{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "406c2750",
   "metadata": {},
   "source": [
    "# Resource Assignment: Optimizing Service Vehicle Allocation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7a7e7404",
   "metadata": {},
   "source": [
    "## Motivation\n",
    "\n",
    "Picture Uber Eats, DoorDash, or Grubhub, but also local mom-and-pop restaurants with their own delivery.   \n",
    "Or consider home service providers that have skilled workers like landscapers, plumbers, or electricians.  \n",
    "Or how about home healthcare providers that send licensed professionals like nurses to patients' homes.\n",
    "\n",
    "What do they all have in common?\n",
    "\n",
    "They all involve delivering goods or services. In these businesses, customers place orders and receive a delivery window from the provider (like when Amazon tells you that your overnight package will arrive between 7 am and 10 am). For service-based businesses, like needing a technician to fix something, customers might also provide an availability window (like, \"Can you come tomorrow afternoon, between 1 pm and 4 pm?\").\n",
    "\n",
    "In these diverse businesses, managing limited resources is the name of the game. Whether it's delivery vans, skilled workers, or even time itself, the challenge lies in allocating these limited resources optimally to achieve business goals."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e1e1d95",
   "metadata": {},
   "source": [
    "## Problem Description\n",
    "\n",
    "Let's delve into a specific scenario: You are consulting for a telecom company that dispatches technicians to perform various tasks for customers, ranging from equipment installations and setups to repairs. Each technician requires a service vehicle to travel to the job site. Here's what you're dealing with:\n",
    "\n",
    "- The company offers various services, and not all technicians can perform all of them, so matching the right technician to the right job is crucial.\n",
    "- Service times (also known as process times) can vary for different jobs.\n",
    "- Customers provide windows of availability, and each customer is assigned to at most one technician (due to resource constraints).\n",
    "- Technicians have their own working hours. Not all of them work an 8-hour shift, and the job can't surpass these hours (no overtime allowed).\n",
    "- Technicians leave the service centers, complete their assigned jobs, and return to the center.\n",
    "- There are a limited number of vans at the service centers, equipped with the necessary tools. These vans are in shorter supply compared to technicians, and each technician needs a van to reach customers.\n",
    "\n",
    "Currently, basic rule-of-thumb approaches are used for scheduling customers one after another and assigning them to the technicians. Each technician is dispatched with a van as soon as their schedule is known. When a technician returns, the van is up for grabs.\n",
    "\n",
    "Now, let's explore how mathematical optimization can help with the allocation of these limited resources."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7f6cde92",
   "metadata": {},
   "source": [
    "## Solution Approach\n",
    "\n",
    "We solve this problem in two steps:\n",
    "\n",
    "### 1. Technician Routing\n",
    "This is a variation of the well-known vehicle routing problem (VRP) with time windows. The goal is to decide which technicians are assigned to which customers and in what sequence. This is modeled and solved in the [`technician_routing`](https://github.com/decision-spot/technician_assignment/blob/main/technician_routing.ipynb) notebook.\n",
    "\n",
    "This model yields two outputs: \n",
    "- `routes` provides some information about each technician's feasible departure window from the service center and their total occupied time.\n",
    "- `orders` provides which customers (or orders) are assigned to which technicians and in what sequence (or in what order). A bit of fun with the file name!\n",
    "\n",
    "_Note:_ The `technician_routing` notebook is almost identical to Gurobi's [`technician_routing_scheduling`](https://colab.research.google.com/github/Gurobi/modeling-examples/blob/master/technician_routing_scheduling/technician_routing_scheduling.ipynb). Since an additional post processing step was required to export the results into csv files, and also some slight modifications in the constraints and objective functions needed to be made, a slightly different file name is used to differentiate between the two. \n",
    "\n",
    "\n",
    "### 2. Resource Allocation\n",
    "Now that we know which technicians serve which customers, we can assign them to the available vans. This is the focus of this notebook.\n",
    "\n",
    "Here, we optimize the allocation of limited resources, ensuring each technician has access to a van equipped with necessary tools to reach customers in time. We're looking at the big picture, reshuffling routes as needed, and making the most of our vans. If a technician can efficiently serve multiple customers, and a service van can be used multiple times per day, we're all in.\n",
    "\n",
    "Let's roll up our sleeves and optimize! 🚚🔧"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ed4f7ee5",
   "metadata": {},
   "source": [
    "# Install Required Packages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "af590656",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-03T18:20:20.280290Z",
     "start_time": "2023-11-03T18:20:20.276772Z"
    }
   },
   "outputs": [],
   "source": [
    "%pip install gurobipy\n",
    "%pip install pandas"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8bd6f69",
   "metadata": {},
   "source": [
    "# Import Packages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "4036b5a7",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:14:49.718106Z",
     "start_time": "2023-11-06T20:14:49.318844Z"
    }
   },
   "outputs": [],
   "source": [
    "import gurobipy as gp\n",
    "import pandas as pd\n",
    "from gurobipy import GRB"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c165d441",
   "metadata": {},
   "source": [
    "# Optimization Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0816abcb",
   "metadata": {},
   "source": [
    "We want to minimize the number of resources used, while maximizing the number of customer orders that we cover (i.e., ensuring that we don't turn down a customer).\n",
    "\n",
    "Note that throughout this notebook, we will use _resource_ and _van_ interchangeably, and similarly, we'll interchange _customer_ and _order_.\n",
    "\n",
    "**Assumptions:**  \n",
    "- All the assumptions are the same as those in the `technician_routing` notebook. \n",
    "- Note: the planning horizon is from 7:00 to 17:00, or 10 hours. The time period is in minutes. So, all the times are translated into minutes starting at 0 minutes and ending at 600 minutes. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "79287692",
   "metadata": {},
   "source": [
    "## Load Required Data"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "817377e0",
   "metadata": {},
   "source": [
    "**Note**:  \n",
    "If you've cloned the repo or downloaded all the files on your machine, you can simply enter the address of the file to read them (e.g., `'routes.csv'`). For consistency, we use the raw file address on GitHub."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "3fd07b80",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:14:50.595803Z",
     "start_time": "2023-11-06T20:14:50.458290Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Route ID</th>\n",
       "      <th>Technician Name</th>\n",
       "      <th>Origin Location</th>\n",
       "      <th>Total Travel Time</th>\n",
       "      <th>Total Processing Time</th>\n",
       "      <th>Total Time</th>\n",
       "      <th>Earliest Start Time</th>\n",
       "      <th>Latest Start Time</th>\n",
       "      <th>Earliest End Time</th>\n",
       "      <th>Latest End Time</th>\n",
       "      <th>Num Jobs</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>Albert</td>\n",
       "      <td>Heidelberg</td>\n",
       "      <td>334.0</td>\n",
       "      <td>90.0</td>\n",
       "      <td>570.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>6.0</td>\n",
       "      <td>570.0</td>\n",
       "      <td>600.0</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>Bob</td>\n",
       "      <td>Heidelberg</td>\n",
       "      <td>100.0</td>\n",
       "      <td>30.0</td>\n",
       "      <td>130.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>100.0</td>\n",
       "      <td>130.0</td>\n",
       "      <td>230.0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>Doris</td>\n",
       "      <td>Freiburg im Breisgau</td>\n",
       "      <td>141.0</td>\n",
       "      <td>120.0</td>\n",
       "      <td>341.0</td>\n",
       "      <td>58.0</td>\n",
       "      <td>178.0</td>\n",
       "      <td>399.0</td>\n",
       "      <td>519.0</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>Ed</td>\n",
       "      <td>Heidelberg</td>\n",
       "      <td>134.0</td>\n",
       "      <td>60.0</td>\n",
       "      <td>194.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>113.0</td>\n",
       "      <td>194.0</td>\n",
       "      <td>307.0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>Flor</td>\n",
       "      <td>Freiburg im Breisgau</td>\n",
       "      <td>90.0</td>\n",
       "      <td>60.0</td>\n",
       "      <td>150.0</td>\n",
       "      <td>195.0</td>\n",
       "      <td>315.0</td>\n",
       "      <td>345.0</td>\n",
       "      <td>465.0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   Route ID Technician Name       Origin Location  Total Travel Time  \\\n",
       "0         1          Albert            Heidelberg              334.0   \n",
       "1         2             Bob            Heidelberg              100.0   \n",
       "2         3           Doris  Freiburg im Breisgau              141.0   \n",
       "3         4              Ed            Heidelberg              134.0   \n",
       "4         5            Flor  Freiburg im Breisgau               90.0   \n",
       "\n",
       "   Total Processing Time  Total Time  Earliest Start Time  Latest Start Time  \\\n",
       "0                   90.0       570.0                  0.0                6.0   \n",
       "1                   30.0       130.0                  0.0              100.0   \n",
       "2                  120.0       341.0                 58.0              178.0   \n",
       "3                   60.0       194.0                  0.0              113.0   \n",
       "4                   60.0       150.0                195.0              315.0   \n",
       "\n",
       "   Earliest End Time  Latest End Time  Num Jobs  \n",
       "0              570.0            600.0         2  \n",
       "1              130.0            230.0         1  \n",
       "2              399.0            519.0         2  \n",
       "3              194.0            307.0         1  \n",
       "4              345.0            465.0         1  "
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "routes = pd.read_csv('https://raw.githubusercontent.com/decision-spot/technician_assignment/main/routes.csv')\n",
    "routes"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "92328709",
   "metadata": {},
   "source": [
    "We can visualize the lengths of the routes by examining the time span between their start and end times. Since each route has a window for the earliest and latest times, we can plot the earliest time a route can start and finish by calculating the difference between \"Earliest End Time\" and \"Earliest Start Time.\" Similarly, we can plot the latest time a route can start and finish by calculating the difference between \"Latest End Time\" and \"Latest Start Time.\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "eb747fc7",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:14:53.371260Z",
     "start_time": "2023-11-06T20:14:52.800192Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA64AAAIhCAYAAABOl+fLAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8pXeV/AAAACXBIWXMAAA9hAAAPYQGoP6dpAABEEklEQVR4nO3dd3gV1d7+/3un9wYJIRAgtEivRwSVIqDUY4GvqCjNFqTIsQIqAQsRFY4ogo8goMeCnkfAdqQJCcIhGJqiWFABQYkoSgIBEpKs3x/+sh83CZBAYFaS9+u65rrYa9ae+exZQbmzZtZ2GWOMAAAAAACwlJfTBQAAAAAAcDoEVwAAAACA1QiuAAAAAACrEVwBAAAAAFYjuAIAAAAArEZwBQAAAABYjeAKAAAAALAawRUAAAAAYDWCKwAAAADAagRXAI5ZuHChXC6Xe/Px8VHNmjV1ww03aOfOnef9/FOnTtXSpUvP+3lK8tfPffI2bNiwcj1X0XXevXu3u23YsGGqV69euZ7nr5y8tqdT0rUoyeTJk+VyufTbb7+d8zmPHj2qyZMnKzU19ZyPdTr//e9/NXnyZB06dOiMfZ955hm5XC5t3LjRo72wsFBRUVFyuVz65ptvPPbl5eUpKChI1113naTSX8uySE1NlcvlOu/XCgBQ8RBcAThuwYIF2rBhg1atWqXRo0frvffe02WXXaY//vjjvJ7X6XA1cOBAbdiwodj2yCOPnPdzP/LII1qyZMl5O77T19YmR48e1ZQpUy5IcJ0yZUqpgmu3bt0kSWvWrPFo/+yzz/THH38oODi42L6NGzfq2LFj7vf27dtXGzZsUM2aNcvnAwAAcBo+ThcAAM2bN1f79u0lSV27dlVBQYGSk5O1dOlSDR8+3OHqzp8aNWrokksuOW/HP3bsmAICAkrc16BBg/N2XtivTZs2ioiIUGpqqsaPH+9uT01NVVxcnLp06aI1a9YoKSnJY5/0f6E3Ojpa0dHRF7RuAEDVxYwrAOsUhdhffvnFo/29995Tx44dFRQUpNDQUPXs2VMbNmzw6HOqW2CLbv0s4nK5lJOTo1deecV9i27Xrl3d+zMzM3XnnXeqdu3a8vPzU0JCgqZMmaL8/HyP486ZM0etWrVSSEiIQkNDddFFF2nixInneAX+z6ZNm3TDDTeoXr16CgwMVL169XTjjTdqz549Hv2KbttcsWKFRowYoejoaAUFBSk3N7fE45Z0nYwxmj17tlq3bq3AwEBFRkZq4MCB+uGHHzz6bd26Vf369VNMTIz8/f0VFxenvn37at++fZLOfG1LMmXKFHXo0EFRUVEKCwtT27Zt9fLLL8sY49GvXr166tevn5YtW6a2bdsqMDBQF110kebPn1/smOnp6br00ksVEBCguLg4TZgwQSdOnDhtHWXx66+/6q677lLTpk0VEhKimJgYXXHFFfrkk0/cfXbv3u0Od1OmTCnxdvCdO3fqpptucl/PJk2a6IUXXvA4V2FhoR5//HElJiYqMDBQERERatmypWbOnCnpz5/v+++/X5KUkJDgPs+pZnm9vLzUuXNnrV+/3uNnOjU1VV27dlWXLl2KvTc1NVXR0dFq1qyZpJJvFe7atauaN2+ujIwMXX755QoKClL9+vX15JNPqrCw0ON4X3/9tXr16qWgoCBVr15dSUlJOnz4cIn1zp8/X61atVJAQICioqJ07bXX6quvvnLv//DDD+VyuZSRkeFue+edd+RyudS3b1+PY7Vs2VIDBgxwv/73v/+tDh06KDw83F3viBEjSqwDAOAcZlwBWGfXrl2SpMaNG7vb3njjDQ0ePFhXXnml3nzzTeXm5uqpp55S165d9fHHH+uyyy4r0zk2bNigK664Qt26dXPfmhsWFibpz9B68cUXy8vLS5MmTVKDBg20YcMGPf7449q9e7cWLFggSVq0aJHuuusujRkzRs8884y8vLz03XffaceOHaWqwRhTLAhLkre3tztk7969W4mJibrhhhsUFRWl/fv3a86cOfrb3/6mHTt2qHr16h7vHTFihPr27at//etfysnJka+vb6mvyZ133qmFCxdq7NixmjZtmn7//Xc9+uij6tSpkz777DPVqFFDOTk56tmzpxISEvTCCy+oRo0ayszM1Jo1a9yh43TX9lR2796tO++8U3Xq1JH0Z+gcM2aMfvrpJ02aNMmj72effaZ7771X48ePV40aNTRv3jzdeuutatiwoTp37ixJ2rFjh7p376569epp4cKFCgoK0uzZs/XGG2+U+nqcye+//y5JSk5OVmxsrI4cOaIlS5a4fya7du2qmjVratmyZerVq5duvfVW3XbbbZLkDrM7duxQp06dVKdOHU2fPl2xsbFavny5xo4dq99++03JycmSpKeeekqTJ0/Www8/rM6dO+vEiRP6+uuv3bcF33bbbfr999/1/PPPa/Hixe7bd5s2bXrK+rt166b33ntPGRkZ6tixowoLC7V27VpNmzZNnTt31oEDB7Rjxw41bdpUeXl52rBhg/r16+fxC6CSZGZmavDgwbr33nuVnJysJUuWaMKECYqLi9OQIUMk/flLqS5dusjX11ezZ89WjRo19Prrr2v06NHFjpeSkqKJEyfqxhtvVEpKig4ePKjJkyerY8eOysjIUKNGjdzHWrVqlf72t79JklatWqXAwEClpaXpxIkT8vX11YEDB/TFF19o5MiRkv78WR00aJAGDRqkyZMnKyAgQHv27NHq1atL9TMAALiADAA4ZMGCBUaSSU9PNydOnDCHDx82y5YtM7GxsaZz587mxIkTxhhjCgoKTFxcnGnRooUpKChwv//w4cMmJibGdOrUyd02dOhQU7du3WLnSk5ONif/Jy84ONgMHTq0WN8777zThISEmD179ni0P/PMM0aS+fLLL40xxowePdpERESc1WeXdMrtX//61ynfl5+fb44cOWKCg4PNzJkz3e1F13LIkCHF3lO0b9euXe62k6/Thg0bjCQzffp0j/fu3bvXBAYGmgceeMAYY8ymTZuMJLN06dLTfr5TXdvSKCgoMCdOnDCPPvqoqVatmiksLHTvq1u3rgkICPAYm2PHjpmoqChz5513utsGDRpkAgMDTWZmprstPz/fXHTRRcWuRUmKfl5+/fXXUtedn59vTpw4Ybp3726uvfZad/uvv/5qJJnk5ORi77nqqqtM7dq1TVZWlkf76NGjTUBAgPn999+NMcb069fPtG7d+rTnf/rpp0v12Yps27bNSDJTp041xhizefNmI8l8/fXXxhhjatSoYWbNmmWMMSYtLc1IMrNnz3a/v6Sfqy5duhhJZuPGjR7natq0qbnqqqvcrx988EHjcrnMtm3bPPr17NnTSDJr1qwxxhjzxx9/mMDAQNOnTx+Pfj/++KPx9/c3N910k7vtsssuM1dccYX7dcOGDc39999vvLy8TFpamjHGmNdff91IMt9++60x5v/+Th86dKhU1wwA4BxuFQbguEsuuUS+vr4KDQ1Vr169FBkZqXfffVc+Pn/eFPLNN9/o559/1i233CIvr//7z1ZISIgGDBig9PR0HT16tNzq+eCDD9StWzfFxcUpPz/fvfXu3VuSlJaWJkm6+OKLdejQId1444169913y7wC7fXXX6+MjIxiW58+fdx9jhw5ogcffFANGzaUj4+PfHx8FBISopycHI9bJYv89RbIsn5ml8ulm2++2eMzx8bGqlWrVu7bRhs2bKjIyEg9+OCDevHFF0s9u3wmq1evVo8ePRQeHi5vb2/5+vpq0qRJOnjwoA4cOODRt3Xr1u6ZWUkKCAhQ48aNPW6fXrNmjbp3764aNWq427y9vTVo0KByqbfIiy++qLZt2yogIEA+Pj7y9fXVxx9/XOLYnOz48eP6+OOPde211yooKMjjuvfp00fHjx9Xenq6pD9/1j777DPdddddWr58ubKzs8+59pYtW6patWrusU1NTVVsbKwSExMlSZ07d3Yv0HTy862nExsbq4svvrjYuU4en2bNmqlVq1Ye/W666SaP1xs2bNCxY8eKrbQdHx+vK664Qh9//LG7rXv37lq/fr2OHTumPXv26LvvvtMNN9yg1q1ba+XKlZL+nIWtU6eOGjVqJEnu2dnrr79eb7/9tn766aczfj4AgDMIrgAc9+qrryojI0OrV6/WnXfeqa+++ko33nije//BgwclqcTVS+Pi4lRYWFiuKxD/8ssvev/99+Xr6+uxFT3bVxRQb7nlFs2fP1979uzRgAEDFBMTow4dOrj/kXwm0dHRat++fbEtKirK3eemm27SrFmzdNttt2n58uX69NNPlZGRoejoaB07dqzYMc92hddffvlFxhjVqFGj2OdOT093f+bw8HClpaWpdevWmjhxopo1a6a4uDglJyef9fOjn376qa688kpJ0ty5c7V+/XplZGTooYcekqRin7NatWrFjuHv7+/R7+DBg4qNjS3Wr6S2szVjxgyNHDlSHTp00DvvvKP09HRlZGSoV69eJY7NyQ4ePKj8/Hw9//zzxa550S8viq77hAkT9Mwzzyg9PV29e/dWtWrV1L17d23atOms63e5XOrSpYvWr1+vEydOaM2aNerSpYt7f5cuXZSWliZjjNasWaPY2FhddNFFZzxueY7Pmf7uF+2XpB49eig3N1fr1q3TypUrVb16dbVp00Y9evTQqlWrJEkff/yxevTo4X5P586dtXTpUuXn52vIkCGqXbu2mjdvrjfffPOMnxMAcGHxjCsAxzVp0sS9IFO3bt1UUFCgefPm6X//9381cOBA9z+E9+/fX+y9P//8s7y8vBQZGSnpz9m3khYkKstsaPXq1dWyZUs98cQTJe6Pi4tz/3n48OEaPny4cnJytHbtWiUnJ6tfv3769ttvVbdu3VKfsyRZWVn64IMPlJyc7LHya25urvv5ypOd6fnDU6levbpcLpc++eQT+fv7F9v/17YWLVpo0aJFMsbo888/18KFC/Xoo48qMDDQo87SWrRokXx9ffXBBx94rIJ8Ll+nU61aNWVmZhZrL6ntbL322mvq2rWr5syZ49F+qgWGThYZGSlvb2/dcsstGjVqVIl9EhISJEk+Pj665557dM899+jQoUNatWqVJk6cqKuuukp79+5VUFDQWX2Gbt26afHixdq4caM++eQTpaSkuPd16dJFv/32mzZv3qz09HRde+21Z3WOkpR2fM70d/+vz3h36NBBISEhWrVqlXbv3q3u3bvL5XKpe/fumj59ujIyMvTjjz96BFdJuvrqq3X11VcrNzdX6enpSklJ0U033aR69eqpY8eO5fFxAQDlgBlXANZ56qmnFBkZqUmTJqmwsFCJiYmqVauW3njjDY9VZnNycvTOO++4VxqW/lx19sCBAx4rEufl5Wn58uXFznPyLFCRfv366YsvvlCDBg1KnBH9a3AtEhwcrN69e+uhhx5SXl6evvzyy3O+Di6XS8aYYkFy3rx5KigoOOfj/1W/fv1kjNFPP/1U4mdu0aJFifW1atVK//znPxUREaEtW7a4953q2pbE5XLJx8dH3t7e7rZjx47pX//611l/nm7duunjjz/2+DkoKCjQW2+9ddbHPJnL5So2Np9//nmxla6L+px8PYKCgtStWzdt3bpVLVu2LPG6lzR7GRERoYEDB2rUqFH6/fff3av6nuo8p1N06+8///lPZWVleaz+3KxZM1WrVk0pKSk6fvx4qW4TLst5v/zyS3322Wce7ScvntWxY0cFBgbqtdde82jft2+fVq9ere7du7vbfH191blzZ61cuVKrV69Wz549JUmXX365fHx89PDDD7uDbEn8/f3VpUsXTZs2TdKfq2cDAOzBjCsA60RGRmrChAl64IEH9MYbb+jmm2/WU089pcGDB6tfv3668847lZubq6efflqHDh3Sk08+6X7voEGDNGnSJN1www26//77dfz4cT333HMlBr0WLVooNTVV77//vmrWrKnQ0FAlJibq0Ucf1cqVK9WpUyeNHTtWiYmJOn78uHbv3q3//Oc/evHFF1W7dm3dfvvtCgwM1KWXXqqaNWsqMzNTKSkpCg8Pdz87dzq//PKL+xnGvwoLC1PTpk0VFhamzp076+mnn1b16tVVr149paWl6eWXX1ZERMQ5XeOTXXrppbrjjjs0fPhwbdq0SZ07d1ZwcLD279+vdevWqUWLFho5cqQ++OADzZ49W9dcc43q168vY4wWL16sQ4cOuYOCdOprW5K+fftqxowZuummm3THHXfo4MGDeuaZZ0qc+S2thx9+WO+9956uuOIKTZo0SUFBQXrhhReUk5NTpuO8//77Cg0NLdY+cOBA9evXT4899piSk5PVpUsXffPNN3r00UeVkJDgsVp0aGio6tatq3fffVfdu3dXVFSUezxnzpypyy67TJdffrlGjhypevXq6fDhw/ruu+/0/vvvu1e37d+/v/v7jqOjo7Vnzx49++yzqlu3rvt5zaJfLsycOVNDhw6Vr6+vEhMTS6y/SLNmzRQTE6MlS5YoOjpaTZo0ce9zuVzq3LmzlixZIql0z7eW1rhx4zR//nz17dtXjz/+uHtV4a+//tqjX0REhB555BFNnDhRQ4YM0Y033qiDBw9qypQpCggIcK+6XKR79+669957Jck9sxoYGKhOnTppxYoVatmypWJiYtz9J02apH379ql79+6qXbu2Dh06pJkzZ8rX19fjtmkAgAUcXBgKQBVXtCppRkZGsX3Hjh0zderUMY0aNTL5+fnGGGOWLl1qOnToYAICAkxwcLDp3r27Wb9+fbH3/uc//zGtW7c2gYGBpn79+mbWrFklriq8bds2c+mll5qgoCAjyXTp0sW979dffzVjx441CQkJxtfX10RFRZl27dqZhx56yBw5csQYY8wrr7xiunXrZmrUqGH8/PxMXFycuf76683nn39+xs+u06wqfOmll7r77du3zwwYMMBERkaa0NBQ06tXL/PFF1+YunXreqzae7prWZpVhYvMnz/fdOjQwQQHB5vAwEDToEEDM2TIELNp0yZjjDFff/21ufHGG02DBg1MYGCgCQ8PNxdffLFZuHBhqa9tSebPn28SExONv7+/qV+/vklJSTEvv/xysbrr1q1r+vbtW+z9Xbp0KXaO9evXm0suucT4+/ub2NhYc//995uXXnqpTKsKn2ozxpjc3Fxz3333mVq1apmAgADTtm1bs3Tp0hKv7apVq0ybNm2Mv7+/keQxdrt27TIjRowwtWrVMr6+viY6Otp06tTJPP744+4+06dPN506dTLVq1c3fn5+pk6dOubWW281u3fv9jjPhAkTTFxcnPHy8vJYnfd0rr/+eiPJDBw4sNi+Z5991kgytWrVKrbvVKsKN2vWrFjfkq7Jjh07TM+ePU1AQICJiooyt956q3n33XdLrHvevHmmZcuWxs/Pz4SHh5urr77avbr3X3322WdGkmnUqJFH+xNPPGEkmXvuucej/YMPPjC9e/c2tWrVMn5+fiYmJsb06dPHfPLJJ8WODQBwlsuYk77dHQAAAAAAi/CMKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFjNx+kCzkVhYaF+/vlnhYaGyuVyOV0OAAAAAIcYY3T48GHFxcXJy4v5ucqmQgfXn3/+WfHx8U6XAQAAAMASe/fuVe3atZ0uA+WsQgfX0NBQSX/+cIaFhTlcDQAAAACnZGdnKz4+3p0RULlU6OBadHtwWFgYwRUAAAAAjxBWUtz8DQAAAACwGsEVAAAAAGA1gisAAAAAwGoV+hlXAAAAACgtY4zy8/NVUFDgdClVnre3t3x8fEr9TDLBFQAAAECll5eXp/379+vo0aNOl4L/X1BQkGrWrCk/P78z9iW4AgAAAKjUCgsLtWvXLnl7eysuLk5+fn6sPuwgY4zy8vL066+/ateuXWrUqJG8vE7/FCvBFQAAAECllpeXp8LCQsXHxysoKMjpciApMDBQvr6+2rNnj/Ly8hQQEHDa/izOBAAAAKBKONOsHi6ssowHIwcAAAAAsBrBFQAAAABgNYIrAAAAAFQxw4YN0zXXXON+3bVrV40bN86xes6E4AoAAAAAlho2bJhcLlexrVevXuV6nsWLF+uxxx4rl2OlpqbK5XLp0KFD5XI8iVWFAQAAAFQxa/c8pj+Of+/Y+SMDGqhz3UdK3b9Xr15asGCBR5u/v/9ZnbugoKDErwKKioo6q+NdKARXAAAAAFXKH8e/14Gc7U6XUWr+/v6KjY0tcd+MGTO0YMEC/fDDD4qKilL//v311FNPKSQkRJK0cOFCjRs3Tq+99poeeOABffvtt9q5c2ex43Tt2lWtW7fWs88+K+nPrxB6+OGH9frrr+vQoUNq3ry5pk2bpq5du0qS9uzZo9GjR2vdunXKy8tTvXr19PTTT6tp06bq1q2bJCkyMlKSNHToUC1cuPCcrgHBFQAAAAAqKC8vLz333HOqV6+edu3apbvuuksPPPCAZs+e7e5z9OhRpaSkaN68eapWrZpiYmLOeNzhw4dr9+7dWrRokeLi4rRkyRL16tVL27dvV6NGjTRq1Cjl5eVp7dq1Cg4O1o4dOxQSEqL4+Hi98847GjBggL755huFhYUpMDDwnD8nwRUAAAAALPbBBx+4Z1CLPPjgg3rkkUc8FlRKSEjQY489ppEjR3oE1xMnTmj27Nlq1apVqc73/fff680339S+ffsUFxcnSbrvvvu0bNkyLViwQFOnTtWPP/6oAQMGqEWLFpKk+vXru99fdNtxTEyMIiIizuYjF0NwBQAAAACLdevWTXPmzPFoKwqHa9as0dSpU7Vjxw5lZ2crPz9fx48fV05OjoKDgyVJfn5+atmyZanPt2XLFhlj1LhxY4/23NxcVatWTZI0duxYjRw5UitWrFCPHj00YMCAMp2jrAiuAAAAAKqUyIAGFer8wcHBatiwYbH2PXv2qE+fPkpKStJjjz2mqKgorVu3TrfeeqtOnDjh7hcYGFjigkynUlhYKG9vb23evFne3t4e+4pmfm+77TZdddVV+vDDD7VixQqlpKRo+vTpGjNmTJk+W2lViuC6cFtnBYZ4n7kjAAAAUAHd3naz0yVUKmVZ0ddmmzZtUn5+vqZPny4vrz+/6fTtt98+5+O2adNGBQUFOnDggC6//PJT9ouPj1dSUpKSkpI0YcIEzZ07V2PGjJGfn5+kP1cwLi+VIrgCAAAAQGWVm5urzMxMjzYfHx81aNBA+fn5ev7559W/f3+tX79eL7744jmfr3Hjxho8eLCGDBmi6dOnq02bNvrtt9+0evVqtWjRQn369NG4cePUu3dvNW7cWH/88YdWr16tJk2aSJLq1q0rl8ulDz74QH369FFgYGCxZ3TLyuucPxUAAAAA4LxZtmyZatas6bFddtllat26tWbMmKFp06apefPmev3115WSklIu51ywYIGGDBmie++9V4mJifr73/+ujRs3Kj4+XtKfs6mjRo1SkyZN1KtXLyUmJroXhKpVq5amTJmi8ePHq0aNGho9evQ51+MyxphzPopDsrOzFR4erplprbhVGAAAAJUWtwqfWVE2yMrKUlhYmMe+48ePa9euXUpISFBAQIBDFeJkZRkXZlwBAAAAAFYjuAIAAAAArEZwBQAAAABYjeAKAAAAALAawRUAAAAAYDWCKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAEsNGzZM11xzzVm9d+HChYqIiCjXelJTU+VyuXTo0KFyPe6Z+FzQswEAAACAw46+954Kf/3VsfN7RUcr6O9/d+z8FREzrgAAAACqlMJff1XBvn2ObeUVmmfMmKEWLVooODhY8fHxuuuuu3TkyBFJf86MDh8+XFlZWXK5XHK5XJo8ebIkKS8vTw888IBq1aql4OBgdejQQampqe7j7tmzR/3791dkZKSCg4PVrFkz/ec//9Hu3bvVrVs3SVJkZKRcLpeGDRtWLp/lTJhxBQAAAIAKyMvLS88995zq1aunXbt26a677tIDDzyg2bNnq1OnTnr22Wc1adIkffPNN5KkkJAQSdLw4cO1e/duLVq0SHFxcVqyZIl69eql7du3q1GjRho1apTy8vK0du1aBQcHa8eOHQoJCVF8fLzeeecdDRgwQN98843CwsIUGBh4QT4rwRUAAAAAKqBx48a5/5yQkKDHHntMI0eO1OzZs+Xn56fw8HC5XC7Fxsa6+33//fd68803tW/fPsXFxUmS7rvvPi1btkwLFizQ1KlT9eOPP2rAgAFq0aKFJKl+/fru90dFRUmSYmJiyv352dMhuAIAAABABbRmzRpNnTpVO3bsUHZ2tvLz83X8+HHl5OQoODi4xPds2bJFxhg1btzYoz03N1fVqlWTJI0dO1YjR47UihUr1KNHDw0YMEAtW7Y875/ndAiuAAAAAKoUr+joCn/+PXv2qE+fPkpKStJjjz2mqKgorVu3TrfeeqtOnDhxyvcVFhbK29tbmzdvlre3t8e+oluJb7vtNl111VX68MMPtWLFCqWkpGj69OkaM2bMOdd9tgiuAAAAAKqUyrCi76ZNm5Sfn6/p06fLy+vPNXfffvttjz5+fn4qKCjwaGvTpo0KCgp04MABXX755ac8fnx8vJKSkpSUlKQJEyZo7ty5GjNmjPz8/CSp2HHPN4IrAAAAAFgsKytL27Zt82iLjo5Wfn6+nn/+efXv31/r16/Xiy++6NGnXr16OnLkiD7++GO1atVKQUFBaty4sQYPHqwhQ4Zo+vTpatOmjX777TetXr1aLVq0UJ8+fTRu3Dj17t1bjRs31h9//KHVq1erSZMmkqS6devK5XLpgw8+UJ8+fRQYGOieqT2f+DocAAAAALBYamqq2rRp47HNnz9fM2bM0LRp09S8eXO9/vrrSklJ8Xhfp06dlJSUpEGDBik6OlpPPfWUJGnBggUaMmSI7r33XiUmJurvf/+7Nm7cqPj4eEl/zqaOGjVKTZo0Ua9evZSYmKjZs2dLkmrVqqUpU6Zo/PjxqlGjhkaPHn1BroHLGGMuyJnOg+zsbIWHh2tmWisFhnif+Q0AAABABXR7281Ol2C9omyQlZWlsLAwj33Hjx/Xrl27lJCQoICAAIcqxMnKMi7MuAIAAAAArFYpnnEd1nptsd+qAAAAAAAqB2ZcAQAAAABWI7gCAAAAAKxGcAUAAABQJVTgdWkrpbKMB8EVAAAAQKXm6+srSTp69KjDleCvisajaHxOp1IszgQAAAAAp+Lt7a2IiAgdOHBAkhQUFCSXy+VwVVWXMUZHjx7VgQMHFBERIW/vM3+1KcEVAAAAQKUXGxsrSe7wCudFRES4x+VMCK4AAAAAKj2Xy6WaNWsqJiZGJ06ccLqcKs/X17dUM61FCK4AAAAAqgxvb+8yBSbYgcWZAAAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1gisAAAAAwGoEVwAAAACA1QiuAAAAAACr+ThdwPmWNWWK0yUAAAAAlU54crLTJaAKcXTGde3aterfv7/i4uLkcrm0dOlSJ8sBAAAAAFjI0eCak5OjVq1aadasWU6WAQAAAACwmKO3Cvfu3Vu9e/d2sgQAAAAAgOUq1DOuubm5ys3Ndb/Ozs52sBoAAAAAwIVQoVYVTklJUXh4uHuLj493uiQAAAAAwHlWoYLrhAkTlJWV5d727t3rdEkAAAAAgPOsQt0q7O/vL39/f6fLAAAAAABcQBVqxhUAAAAAUPU4OuN65MgRfffdd+7Xu3bt0rZt2xQVFaU6deo4WBkAAAAAwBaOBtdNmzapW7du7tf33HOPJGno0KFauHChQ1UBAAAAAGziaHDt2rWrjDFOlgAAAAAAsBzPuAIAAAAArEZwBQAAAABYjeAKAAAAALAawRUAAAAAYDWCKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAq/k4XcD5Fp6c7HQJAAAAAIBzwIwrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1gisAAAAAwGoEVwAAAACA1QiuAAAAAACrEVwBAAAAAFYjuAIAAAAArEZwBQAAAABYjeAKAAAAALAawRUAAAAAYDUfpwsoDwu3dVZgiLfTZaAKur3tZqdLAAAAACo9ZlwBAAAAAFYjuAIAAAAArEZwBQAAAABYjeAKAAAAALAawRUAAAAAYDWCKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1gisAAAAAwGoEVwAAAACA1QiuAAAAAACrEVwBAAAAAFbzcbqA8jCs9VqFhYU5XQYAAAAA4DxgxhUAAAAAYDWCKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1HydPnpKSosWLF+vrr79WYGCgOnXqpGnTpikxMdHJsmCprClTnC4BVVh4crLTJQAAAFRZjs64pqWladSoUUpPT9fKlSuVn5+vK6+8Ujk5OU6WBQAAAACwiKMzrsuWLfN4vWDBAsXExGjz5s3q3LmzQ1UBAAAAAGziaHA9WVZWliQpKiqqxP25ubnKzc11v87Ozr4gdQEAAAAAnGPN4kzGGN1zzz267LLL1Lx58xL7pKSkKDw83L3Fx8df4CoBAAAAABeaNcF19OjR+vzzz/Xmm2+ess+ECROUlZXl3vbu3XsBKwQAAAAAOMGKW4XHjBmj9957T2vXrlXt2rVP2c/f31/+/v4XsDIAAAAAgNMcDa7GGI0ZM0ZLlixRamqqEhISnCwHAAAAAGAhR4PrqFGj9MYbb+jdd99VaGioMjMzJUnh4eEKDAx0sjQAAAAAgCUcfcZ1zpw5ysrKUteuXVWzZk339tZbbzlZFgAAAADAIo7fKgwAAAAAwOlYs6owAAAAAAAlIbgCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1gisAAAAAwGoEVwAAAACA1QiuAAAAAACrEVwBAAAAAFYjuAIAAAAArEZwBQAAAABYjeAKAAAAALAawRUAAAAAYDWCKwAAAADAagRXAAAAAIDVfJwuACit8ORkp0sAAAAA4ABmXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1gisAAAAAwGoEVwAAAACA1QiuAAAAAACrEVwBAAAAAFbzcboAnF9zt7RzugQAQBV3e9vNTpcAAKjgmHEFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAq5X563B27typd999V7t375bL5VJCQoKuueYa1a9f/3zUBwAAAACo4soUXFNSUjRp0iQVFhYqJiZGxhj9+uuvGj9+vKZOnar77rvvfNUJAAAAAKiiSn2r8Jo1a/Twww/roYce0m+//ab9+/crMzPTHVzHjx+vtWvXns9aAQAAAABVkMsYY0rTcdCgQYqIiND//M//lLj/jjvu0OHDh/Xmm2+Wa4Gnk52drfDwcGVlZSksLOyCnbcimbulndMlAACquNvbbna6BABVANmgciv1jOunn36qW2655ZT7b7nlFqWnp5dLUQAAAAAAFCl1cP3ll19Ur169U+5PSEhQZmZmedQEAAAAAIBbqYPr8ePH5efnd8r9vr6+ysvLK5eiAAAAAAAoUqZVhefNm6eQkJAS9x0+fLhcCgIAAAAA4K9KHVzr1KmjuXPnnrEPAAAAAADlqdTBdffu3eexDAAAAAAASlbqZ1wBAAAAAHBCqWdcn3vuuVL1Gzt27FkXAwAAAADAyUodXP/5z3+esY/L5SK4AgAAAADKVamD665du85nHQAAAAAAlIhnXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgtVKvKvxX33//vRYsWKDvv/9eM2fOVExMjJYtW6b4+Hg1a9asvGvEObi97WanSwAAAACAc1LmGde0tDS1aNFCGzdu1OLFi3XkyBFJ0ueff67k5ORyLxAAAAAAULWVObiOHz9ejz/+uFauXCk/Pz93e7du3bRhw4ZyLQ4AAAAAgDIH1+3bt+vaa68t1h4dHa2DBw+WS1EAAAAAABQpc3CNiIjQ/v37i7Vv3bpVtWrVKpeiAAAAAAAoUubgetNNN+nBBx9UZmamXC6XCgsLtX79et13330aMmTI+agRAAAAAFCFlTm4PvHEE6pTp45q1aqlI0eOqGnTpurcubM6deqkhx9++HzUCAAAAACowlzGGHM2b/zhhx+0ZcsWFRYWqk2bNmrUqFF513ZG2dnZCg8PV1ZWlsLCwi74+QEAAADYgWxQuZV5xvXRRx/V0aNHVb9+fQ0cOFDXX3+9GjVqpGPHjunRRx89HzUCAAAAAKqwMs+4ent7a//+/YqJifFoP3jwoGJiYlRQUFCuBZ4Ov1UBAAAAIJENKrsyz7gaY+RyuYq1f/bZZ4qKiiqXogAAAAAAKOJT2o6RkZFyuVxyuVxq3LixR3gtKCjQkSNHlJSUdF6KBAAAAABUXaUOrs8++6yMMRoxYoSmTJmi8PBw9z4/Pz/Vq1dPHTt2PC9FAgAAAACqrlIH16FDh0qSEhIS1KlTJ/n6+p63ogAAAAAAKFLq4FokISFB+/fvP+X+OnXqnFNBAAAAAAD8VZmDa7169UpcnKnIhVxVGAAAAABQ+ZU5uG7dutXj9YkTJ7R161bNmDFDTzzxRLkVBgAAAACAdBbBtVWrVsXa2rdvr7i4OD399NO67rrryqUwAHbJmjLF6RIAAFB4crLTJQBwQJm/x/VUGjdurIyMjDK9Z86cOWrZsqXCwsIUFhamjh076qOPPiqvkgAAAAAAlUCZZ1yzs7M9XhtjtH//fk2ePFmNGjUq07Fq166tJ598Ug0bNpQkvfLKK7r66qu1detWNWvWrKylAQAAAAAqoTIH14iIiGKLMxljFB8fr0WLFpXpWP379/d4/cQTT2jOnDlKT08nuAIAAAAAJJ1FcF2zZo3Hay8vL0VHR6thw4by8Snz4dwKCgr073//Wzk5OerYsWOJfXJzc5Wbm+t+ffLsLwAAAACg8ilz0uzSpUu5FrB9+3Z17NhRx48fV0hIiJYsWaKmTZuW2DclJUVTWCAGAAAAAKqUs1qc6fvvv9eYMWPUo0cP9ezZU2PHjtX3339/VgUkJiZq27ZtSk9P18iRIzV06FDt2LGjxL4TJkxQVlaWe9u7d+9ZnRMAAAAAUHGUObguX75cTZs21aeffqqWLVuqefPm2rhxo5o1a6aVK1eWuQA/Pz81bNhQ7du3V0pKilq1aqWZM2eW2Nff39+9AnHRBgAAAACo3Mp8q/D48eP1j3/8Q08++WSx9gcffFA9e/Y8p4KMMR7PsQIAAAAAqrYyB9evvvpKb7/9drH2ESNG6Nlnny3TsSZOnKjevXsrPj5ehw8f1qJFi5Samqply5aVtSwAAAAAQCVV5uAaHR2tbdu2FfvO1m3btikmJqZMx/rll190yy23aP/+/QoPD1fLli21bNmyc561BQAAAABUHmUOrrfffrvuuOMO/fDDD+rUqZNcLpfWrVunadOm6d577y3TsV5++eWynh4AAAAAUMWUObg+8sgjCg0N1fTp0zVhwgRJUlxcnCZPnqyxY8eWe4EAAAAAgKqtzMHV5XLpH//4h/7xj3/o8OHDkqTQ0FBJ0k8//aRatWqVb4UAAAAAgCrtrL7HtUhoaKhCQ0OVmZmpMWPGqGHDhuVVFwAAAAAAksoQXA8dOqTBgwcrOjpacXFxeu6551RYWKhJkyapfv36Sk9P1/z5889nrQAAAACAKqjUtwpPnDhRa9eu1dChQ7Vs2TL94x//0LJly3T8+HF99NFH6tKly/msEwAAAABQRZU6uH744YdasGCBevToobvuuksNGzZU48aNy/zdrQAAAAAAlEWpbxX++eef1bRpU0lS/fr1FRAQoNtuu+28FQYAAAAAgFSG4FpYWChfX1/3a29vbwUHB5+XogAAAAAAKFLqW4WNMRo2bJj8/f0lScePH1dSUlKx8Lp48eLyrRAAAAAAUKWVOrgOHTrU4/XNN99c7sUAAAAAAHCyUgfXBQsWnM86AAAAAAAoUamfcQUAAAAAwAkEVwAAAACA1QiuAAAAAACrEVwBAAAAAFYr9eJMAKq28ORkp0sAAABAFcWMKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1H6cLKA8Lt3VWYIi302UAKIPb2252ugQAAABUEMy4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1gisAAAAAwGoEVwAAAACA1QiuAAAAAACrEVwBAAAAAFYjuAIAAAAArEZwBQAAAABYjeAKAAAAALAawRUAAAAAYDWCKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACs5uN0AeVhWOu1CgsLc7oMAAAAAMB5wIwrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1gisAAAAAwGoEVwAAAACA1QiuAAAAAACrEVwBAAAAAFYjuAIAAAAArEZwBQAAAABYjeAKAAAAALAawRUAAAAAYDWCKwAAAADAaj5OF1AkJSVFEydO1N13361nn33W6XJQCWVNmeJ0CQDOQnhystMlAAAAh1kx45qRkaGXXnpJLVu2dLoUAAAAAIBlHA+uR44c0eDBgzV37lxFRkY6XQ4AAAAAwDKOB9dRo0apb9++6tGjxxn75ubmKjs722MDAAAAAFRujj7jumjRIm3ZskUZGRml6p+SkqIpPKcIAAAAAFWKYzOue/fu1d13363XXntNAQEBpXrPhAkTlJWV5d727t17nqsEAAAAADjNsRnXzZs368CBA2rXrp27raCgQGvXrtWsWbOUm5srb29vj/f4+/vL39//QpcKAAAAAHCQY8G1e/fu2r59u0fb8OHDddFFF+nBBx8sFloBAAAAAFWTY8E1NDRUzZs392gLDg5WtWrVirUDAAAAAKoux1cVBgAAAADgdBxdVfhkqampTpcAAAAAALAMM64AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1gisAAAAAwGo+ThcAXCjhyclOlwAAAADgLDDjCgAAAACwGsEVAAAAAGA1gisAAAAAwGoEVwAAAACA1QiuAAAAAACrEVwBAAAAAFYjuAIAAAAArEZwBQAAAABYjeAKAAAAALAawRUAAAAAYDWCKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsJqP0wUAqLrmbmnndAnAeXV7281OlwAAQKXAjCsAAAAAwGoEVwAAAACA1QiuAAAAAACrEVwBAAAAAFYjuAIAAAAArEZwBQAAAABYjeAKAAAAALAawRUAAAAAYDWCKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1gisAAAAAwGo+ThcAoOq6ve1mp0sAAABABcCMKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1H6cLAACgPGRNmeJ0CcB5E56c7HQJAOAoR2dcJ0+eLJfL5bHFxsY6WRIAAAAAwDKOz7g2a9ZMq1atcr/29vZ2sBoAAAAAgG0cD64+Pj7MsgIAAAAATsnxxZl27typuLg4JSQk6IYbbtAPP/xwyr65ubnKzs722AAAAAAAlZujwbVDhw569dVXtXz5cs2dO1eZmZnq1KmTDh48WGL/lJQUhYeHu7f4+PgLXDEAAAAA4EJzGWOM00UUycnJUYMGDfTAAw/onnvuKbY/NzdXubm57tfZ2dmKj49XVlaWwsLCLmSpAADLsKowKjNWFQbOLDs7W+Hh4WSDSsrxZ1z/Kjg4WC1atNDOnTtL3O/v7y9/f/8LXBUAAAAAwEmOP+P6V7m5ufrqq69Us2ZNp0sBAAAAAFjC0eB63333KS0tTbt27dLGjRs1cOBAZWdna+jQoU6WBQAAAACwiKO3Cu/bt0833nijfvvtN0VHR+uSSy5Renq66tat62RZAAAAAACLOBpcFy1a5OTpAQAAAAAVgFXPuAIAAAAAcDKCKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAAAABWI7gCAAAAAKxGcAUAAAAAWM3H6QIAACgP4cnJTpcAAADOE2ZcAQAAAABWI7gCAAAAAKxGcAUAAAAAWI3gCgAAAACwGsEVAAAAAGA1gisAAAAAwGoEVwAAAACA1QiuAAAAAACrEVwBAAAAAFYjuAIAAAAArEZwBQAAAABYjeAKAAAAALAawRUAAAAAYDWCKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFjNx+kCzoUxRpKUnZ3tcCUAAAAAnFSUCYoyAiqXCh1cDx48KEmKj493uBIAAAAANjh8+LDCw8OdLgPlrEIH16ioKEnSjz/+yA9nJZedna34+Hjt3btXYWFhTpeD84ixrjoY66qDsa46GOuqw8axNsbo8OHDiouLc7oUnAcVOrh6ef35iG54eLg1f2FwfoWFhTHWVQRjXXUw1lUHY111MNZVh21jzWRW5cXiTAAAAAAAqxFcAQAAAABWq9DB1d/fX8nJyfL393e6FJxnjHXVwVhXHYx11cFYVx2MddXBWONCcxnWiwYAAAAAWKxCz7gCAAAAACo/gisAAAAAwGoEVwAAAACA1QiuAAAAAACrVejgOnv2bCUkJCggIEDt2rXTJ5984nRJKIO1a9eqf//+iouLk8vl0tKlSz32G2M0efJkxcXFKTAwUF27dtWXX37p0Sc3N1djxoxR9erVFRwcrL///e/at2/fBfwUKI2UlBT97W9/U2hoqGJiYnTNNdfom2++8ejDeFcOc+bMUcuWLd1fSN+xY0d99NFH7v2Mc+WVkpIil8ulcePGudsY78ph8uTJcrlcHltsbKx7P+Ncufz000+6+eabVa1aNQUFBal169bavHmzez/jDadU2OD61ltvady4cXrooYe0detWXX755erdu7d+/PFHp0tDKeXk5KhVq1aaNWtWifufeuopzZgxQ7NmzVJGRoZiY2PVs2dPHT582N1n3LhxWrJkiRYtWqR169bpyJEj6tevnwoKCi7Ux0AppKWladSoUUpPT9fKlSuVn5+vK6+8Ujk5Oe4+jHflULt2bT355JPatGmTNm3apCuuuEJXX321+x81jHPllJGRoZdeekktW7b0aGe8K49mzZpp//797m379u3ufYxz5fHHH3/o0ksvla+vrz766CPt2LFD06dPV0REhLsP4w3HmArq4osvNklJSR5tF110kRk/frxDFeFcSDJLlixxvy4sLDSxsbHmySefdLcdP37chIeHmxdffNEYY8yhQ4eMr6+vWbRokbvPTz/9ZLy8vMyyZcsuWO0ouwMHDhhJJi0tzRjDeFd2kZGRZt68eYxzJXX48GHTqFEjs3LlStOlSxdz9913G2P4e12ZJCcnm1atWpW4j3GuXB588EFz2WWXnXI/4w0nVcgZ17y8PG3evFlXXnmlR/uVV16p//73vw5VhfK0a9cuZWZmeoyxv7+/unTp4h7jzZs368SJEx594uLi1Lx5c34OLJeVlSVJioqKksR4V1YFBQVatGiRcnJy1LFjR8a5kho1apT69u2rHj16eLQz3pXLzp07FRcXp4SEBN1www364YcfJDHOlc17772n9u3b6//9v/+nmJgYtWnTRnPnznXvZ7zhpAoZXH/77TcVFBSoRo0aHu01atRQZmamQ1WhPBWN4+nGODMzU35+foqMjDxlH9jHGKN77rlHl112mZo3by6J8a5stm/frpCQEPn7+yspKUlLlixR06ZNGedKaNGiRdqyZYtSUlKK7WO8K48OHTro1Vdf1fLlyzV37lxlZmaqU6dOOnjwIONcyfzwww+aM2eOGjVqpOXLlyspKUljx47Vq6++Kom/13CWj9MFnAuXy+Xx2hhTrA0V29mMMT8Hdhs9erQ+//xzrVu3rtg+xrtySExM1LZt23To0CG98847Gjp0qNLS0tz7GefKYe/evbr77ru1YsUKBQQEnLIf413x9e7d2/3nFi1aqGPHjmrQoIFeeeUVXXLJJZIY58qisLBQ7du319SpUyVJbdq00Zdffqk5c+ZoyJAh7n6MN5xQIWdcq1evLm9v72K/tTlw4ECx3wChYiparfB0YxwbG6u8vDz98ccfp+wDu4wZM0bvvfee1qxZo9q1a7vbGe/Kxc/PTw0bNlT79u2VkpKiVq1aaebMmYxzJbN582YdOHBA7dq1k4+Pj3x8fJSWlqbnnntOPj4+7vFivCuf4OBgtWjRQjt37uTvdSVTs2ZNNW3a1KOtSZMm7sVPGW84qUIGVz8/P7Vr104rV670aF+5cqU6derkUFUoTwkJCYqNjfUY47y8PKWlpbnHuF27dvL19fXos3//fn3xxRf8HFjGGKPRo0dr8eLFWr16tRISEjz2M96VmzFGubm5jHMl0717d23fvl3btm1zb+3bt9fgwYO1bds21a9fn/GupHJzc/XVV1+pZs2a/L2uZC699NJiX1f37bffqm7dupL4/zUcduHXgyofixYtMr6+vubll182O3bsMOPGjTPBwcFm9+7dTpeGUjp8+LDZunWr2bp1q5FkZsyYYbZu3Wr27NljjDHmySefNOHh4Wbx4sVm+/bt5sYbbzQ1a9Y02dnZ7mMkJSWZ2rVrm1WrVpktW7aYK664wrRq1crk5+c79bFQgpEjR5rw8HCTmppq9u/f796OHj3q7sN4Vw4TJkwwa9euNbt27TKff/65mThxovHy8jIrVqwwxjDOld1fVxU2hvGuLO69916TmppqfvjhB5Oenm769etnQkND3f/mYpwrj08//dT4+PiYJ554wuzcudO8/vrrJigoyLz22mvuPow3nFJhg6sxxrzwwgumbt26xs/Pz7Rt29b91RqoGNasWWMkFduGDh1qjPlzyfXk5GQTGxtr/P39TefOnc327ds9jnHs2DEzevRoExUVZQIDA02/fv3Mjz/+6MCnwemUNM6SzIIFC9x9GO/KYcSIEe7/LkdHR5vu3bu7Q6sxjHNld3JwZbwrh0GDBpmaNWsaX19fExcXZ6677jrz5ZdfuvczzpXL+++/b5o3b278/f3NRRddZF566SWP/Yw3nOIyxhhn5noBAAAAADizCvmMKwAAAACg6iC4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAqxFcAQAVwuTJk9W6dWunywAAAA5wGWOM00UAAKo2l8t12v1Dhw7VrFmzlJubq2rVql2gqgAAgC0IrgAAx2VmZrr//NZbb2nSpEn65ptv3G2BgYEKDw93ojQAAGABbhUGADguNjbWvYWHh8vlchVrO/lW4WHDhumaa67R1KlTVaNGDUVERGjKlCnKz8/X/fffr6ioKNWuXVvz58/3ONdPP/2kQYMGKTIyUtWqVdPVV1+t3bt3X9gPDAAAyoTgCgCosFavXq2ff/5Za9eu1YwZMzR58mT169dPkZGR2rhxo5KSkpSUlKS9e/dKko4ePapu3bopJCREa9eu1bp16xQSEqJevXopLy/P4U8DAABOheAKAKiwoqKi9NxzzykxMVEjRoxQYmKijh49qokTJ6pRo0aaMGGC/Pz8tH79eknSokWL5OXlpXnz5qlFixZq0qSJFixYoB9//FGpqanOfhgAAHBKPk4XAADA2WrWrJm8vP7vd7A1atRQ8+bN3a+9vb1VrVo1HThwQJK0efNmfffddwoNDfU4zvHjx/X9999fmKIBAECZEVwBABWWr6+vx2uXy1ViW2FhoSSpsLBQ7dq10+uvv17sWNHR0eevUAAAcE4IrgCAKqNt27Z66623FBMTo7CwMKfLAQAApcQzrgCAKmPw4MGqXr26rr76an3yySfatWuX0tLSdPfdd2vfvn1OlwcAAE6B4AoAqDKCgoK0du1a1alTR9ddd52aNGmiESNG6NixY8zAAgBgMZcxxjhdBAAAAAAAp8KMKwAAAADAagRXAAAAAIDVCK4AAAAAAKsRXAEAAAAAViO4AgAAAACsRnAFAAAAAFiN4AoAAAAAsBrBFQAAAABgNYIrAAAAAMBqBFcAAAAAgNUIrgAAAAAAq/1/3Mvgl3TffakAAAAASUVORK5CYII=",
      "text/plain": [
       "<Figure size 1000x600 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "fig, ax = plt.subplots(figsize=(10, 6))\n",
    "row_height = 0.3\n",
    "row_space = 0.2\n",
    "\n",
    "for _, row in routes.iterrows():\n",
    "    route_id = row[\"Route ID\"]\n",
    "    earliest_start = row[\"Earliest Start Time\"]\n",
    "    earliest_end = row[\"Earliest End Time\"]\n",
    "    latest_start = row[\"Latest Start Time\"]\n",
    "    latest_end = row[\"Latest End Time\"]\n",
    "\n",
    "    # Plot the bars for earliest start to earliest end\n",
    "    ax.barh(route_id - row_space / 2 - row_height, earliest_end - earliest_start, \n",
    "            left=earliest_start, height=row_height, color=\"yellowgreen\")\n",
    "\n",
    "    # Plot the bars for latest start to latest end on a separate line\n",
    "    ax.barh(route_id + row_space / 2, latest_end - latest_start, \n",
    "            left=latest_start, height=row_height, color=\"lightcoral\")\n",
    "\n",
    "# Labels\n",
    "ax.set_xlabel(\"Time\")\n",
    "ax.set_ylabel(\"Route ID\")\n",
    "ax.set_title(\"Routes Earliest and Latest Windows\")\n",
    "ax.invert_yaxis()  # Invert the y-axis to have Route ID 1 at the top\n",
    "# Set y-ticks to ensure integer values\n",
    "ax.set_yticks(range(1, len(routes) + 1))\n",
    "# Create a single legend entry \n",
    "earliest_legend = plt.Line2D([0], [0], color=\"yellowgreen\", lw=4, label=\"Earliest\")\n",
    "latest_legend = plt.Line2D([0], [0], color=\"lightcoral\", lw=4, label=\"Latest\")\n",
    "ax.legend(handles=[earliest_legend, latest_legend], loc=\"upper left\", bbox_to_anchor=(1, 1))\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e294c161",
   "metadata": {},
   "source": [
    "The length of each bar represents the duration from the start to the completion of a route. Because we have time windows (both earliest and latest times) for both the start and finish, each route is represented by two bars. One bar illustrates the route's duration if everything starts at the earliest times, and the other shows the duration if everything is delayed until the latest times. By comparing the starting points of these bars for each route, we can assess the schedule flexibility for each route.\n",
    "\n",
    "We can see that some routes, like route 1, have a very tight schedule, while routes like 3 and 4, have more room for their start times. Our goal is now more clear. Is it possible to take advantage of the extra rooms in the routes' schedules and assign multiple routes to the same van, thus, reducing the number of resources?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "2d6872ea",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:15:02.298171Z",
     "start_time": "2023-11-06T20:15:02.119337Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Route ID</th>\n",
       "      <th>Stop Number</th>\n",
       "      <th>Customer Name</th>\n",
       "      <th>Technician Name</th>\n",
       "      <th>Location Name</th>\n",
       "      <th>Job type</th>\n",
       "      <th>Processing Time</th>\n",
       "      <th>Customer Time Window Start</th>\n",
       "      <th>Customer Time Window End</th>\n",
       "      <th>Earliest Start</th>\n",
       "      <th>Latest Start</th>\n",
       "      <th>Earliest End</th>\n",
       "      <th>Latest End</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>Customer1</td>\n",
       "      <td>Albert</td>\n",
       "      <td>Mannheim</td>\n",
       "      <td>Equipment Setup</td>\n",
       "      <td>30.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>30.0</td>\n",
       "      <td>24.0</td>\n",
       "      <td>30.0</td>\n",
       "      <td>54.0</td>\n",
       "      <td>60.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>Customer7</td>\n",
       "      <td>Albert</td>\n",
       "      <td>Loerrach</td>\n",
       "      <td>Inspect/Service Equipment</td>\n",
       "      <td>60.0</td>\n",
       "      <td>360.0</td>\n",
       "      <td>480.0</td>\n",
       "      <td>360.0</td>\n",
       "      <td>390.0</td>\n",
       "      <td>420.0</td>\n",
       "      <td>450.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>Customer2</td>\n",
       "      <td>Bob</td>\n",
       "      <td>Karlsruhe</td>\n",
       "      <td>Equipment Setup</td>\n",
       "      <td>30.0</td>\n",
       "      <td>30.0</td>\n",
       "      <td>150.0</td>\n",
       "      <td>50.0</td>\n",
       "      <td>150.0</td>\n",
       "      <td>80.0</td>\n",
       "      <td>180.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>Customer4</td>\n",
       "      <td>Doris</td>\n",
       "      <td>Buehl</td>\n",
       "      <td>Equipment Installation</td>\n",
       "      <td>60.0</td>\n",
       "      <td>120.0</td>\n",
       "      <td>240.0</td>\n",
       "      <td>120.0</td>\n",
       "      <td>240.0</td>\n",
       "      <td>180.0</td>\n",
       "      <td>300.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>Customer6</td>\n",
       "      <td>Doris</td>\n",
       "      <td>Lahr/Schwarzwald</td>\n",
       "      <td>Repair - Critical</td>\n",
       "      <td>60.0</td>\n",
       "      <td>300.0</td>\n",
       "      <td>420.0</td>\n",
       "      <td>300.0</td>\n",
       "      <td>420.0</td>\n",
       "      <td>360.0</td>\n",
       "      <td>480.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>4</td>\n",
       "      <td>1</td>\n",
       "      <td>Customer3</td>\n",
       "      <td>Ed</td>\n",
       "      <td>Baden-Baden</td>\n",
       "      <td>Repair - Regular</td>\n",
       "      <td>60.0</td>\n",
       "      <td>60.0</td>\n",
       "      <td>180.0</td>\n",
       "      <td>67.0</td>\n",
       "      <td>180.0</td>\n",
       "      <td>127.0</td>\n",
       "      <td>240.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>5</td>\n",
       "      <td>1</td>\n",
       "      <td>Customer5</td>\n",
       "      <td>Flor</td>\n",
       "      <td>Offenburg</td>\n",
       "      <td>Equipment Installation</td>\n",
       "      <td>60.0</td>\n",
       "      <td>240.0</td>\n",
       "      <td>360.0</td>\n",
       "      <td>240.0</td>\n",
       "      <td>360.0</td>\n",
       "      <td>300.0</td>\n",
       "      <td>420.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   Route ID  Stop Number Customer Name Technician Name     Location Name  \\\n",
       "0         1            1     Customer1          Albert          Mannheim   \n",
       "1         1            2     Customer7          Albert          Loerrach   \n",
       "2         2            1     Customer2             Bob         Karlsruhe   \n",
       "3         3            1     Customer4           Doris             Buehl   \n",
       "4         3            2     Customer6           Doris  Lahr/Schwarzwald   \n",
       "5         4            1     Customer3              Ed       Baden-Baden   \n",
       "6         5            1     Customer5            Flor         Offenburg   \n",
       "\n",
       "                    Job type  Processing Time  Customer Time Window Start  \\\n",
       "0            Equipment Setup             30.0                         0.0   \n",
       "1  Inspect/Service Equipment             60.0                       360.0   \n",
       "2            Equipment Setup             30.0                        30.0   \n",
       "3     Equipment Installation             60.0                       120.0   \n",
       "4          Repair - Critical             60.0                       300.0   \n",
       "5           Repair - Regular             60.0                        60.0   \n",
       "6     Equipment Installation             60.0                       240.0   \n",
       "\n",
       "   Customer Time Window End  Earliest Start  Latest Start  Earliest End  \\\n",
       "0                      30.0            24.0          30.0          54.0   \n",
       "1                     480.0           360.0         390.0         420.0   \n",
       "2                     150.0            50.0         150.0          80.0   \n",
       "3                     240.0           120.0         240.0         180.0   \n",
       "4                     420.0           300.0         420.0         360.0   \n",
       "5                     180.0            67.0         180.0         127.0   \n",
       "6                     360.0           240.0         360.0         300.0   \n",
       "\n",
       "   Latest End  \n",
       "0        60.0  \n",
       "1       450.0  \n",
       "2       180.0  \n",
       "3       300.0  \n",
       "4       480.0  \n",
       "5       240.0  \n",
       "6       420.0  "
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "order_routes = pd.read_csv('https://raw.githubusercontent.com/decision-spot/technician_assignment/main/orders.csv')\n",
    "order_routes"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b8e9dc1",
   "metadata": {},
   "source": [
    "Note that \"Earliest Start\" and \"Latest Start\" consider the travel time from the Depot to the Customer. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "190b9bce",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:15:04.079394Z",
     "start_time": "2023-11-06T20:15:04.072783Z"
    }
   },
   "outputs": [],
   "source": [
    "earliest_time = 0  # this is the reference for start time. Assume 7:00 AM is minute 0\n",
    "latest_time = 600  # 10 hours later, 5:00 PM is minute 600\n",
    "resource_limit = 3  # number of available resources"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75881443",
   "metadata": {},
   "source": [
    "## Problem Formulation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8b8229be",
   "metadata": {},
   "source": [
    "Let's define our notations for the MO model.\n",
    "\n",
    "**Sets**\n",
    "- $O\\quad$: Set of orders\n",
    "- $R\\quad$: Set of routes\n",
    "- $V\\quad$: Set of resources/vans\n",
    "\n",
    "We also have the following information from `routes` and `order_routes` dataframes:\n",
    "\n",
    "**Parameters**\n",
    "- $b^{E}_{r}\\quad$: earliest start (beginning) time of route $r \\in R$\n",
    "- $b^{L}_{r}\\quad$: latest start (beginning) time of route $r \\in R$\n",
    "- $f^{E}_{r}\\quad$: earliest end (finish) time of route $r \\in R$\n",
    "- $f^{L}_{r}\\quad$: latest end (finish) time of route $r \\in R$\n",
    "- $t_{r}\\quad$: total duration of time on route $r \\in R$\n",
    "- $a_{o,r}\\quad$: 1 if order $o \\in O$ is covered by route $r \\in R$\n",
    "\n",
    "Total time ($t_{r}$) includes all the transit time, processing time, and any waiting time from the start (leaving the depot) to the end (returning to the depot) for each route.\n",
    "\n",
    "Note that superscript $E$ is used to indicate earliest and $L$ is used to indicate latest time. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9fcf3cf8",
   "metadata": {},
   "source": [
    "## Decision Variables"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d21f6f93",
   "metadata": {},
   "source": [
    "First of all, we know that due to resource limitation, we may not be able to use every route, and consequently, cover every order. So, we want to have variables that track the order coverage and route usage: \n",
    "- $u_{o}\\quad$: 1 if order $o \\in O$ is covered; 0 otherwise\n",
    "- $x_{r}\\quad$: 1 if route $r \\in R$ is used; 0 otherwise\n",
    "\n",
    "Next, we want to know which of the available vans are used and track which route is assigned to which van:\n",
    "- $y_{r,v}\\quad$: 1 if route $r \\in R$ is assigned to van $v \\in V$; 0 otherwise\n",
    "- $z_{v}\\quad$: 1 if van $v \\in V$ is used; 0 otherwise\n",
    "\n",
    "As explained before, we want to see if it's possible to take advantage of the route's start time flexibility and shift the routes around as needed. That way, more routes can be assigned to a single van. That means, the start time of a route (and by extension its end time) are decision variables too:\n",
    "- $s_{r}\\quad$: start time of route $r \\in R$\n",
    "- $e_{r}\\quad$: end time of route $r \\in R$\n",
    "\n",
    "With these initial decision variables, we can start the MO model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "e8140631",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:15:06.579519Z",
     "start_time": "2023-11-06T20:15:06.566634Z"
    }
   },
   "outputs": [],
   "source": [
    "order_route_dict = dict(zip(order_routes['Customer Name'], order_routes['Route ID']))  # a(o,r)\n",
    "routes_dict = routes.set_index('Route ID').to_dict(orient='index')  # this will help us in creating the constraints\n",
    "r_set = routes_dict.keys()  # R\n",
    "v_set = set(range(resource_limit))  # V\n",
    "rv_set = {(r, v) for r in r_set for v in range(resource_limit)}  # pair of (r,v) index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "18f9b67f",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:15:09.709023Z",
     "start_time": "2023-11-06T20:15:09.701261Z"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "mdl = gp.Model('resource_assignment')\n",
    "\n",
    "# Variables\n",
    "u = mdl.addVars(order_route_dict.keys(), vtype=GRB.BINARY, name='u')  # tracks whether order o is covered\n",
    "x = mdl.addVars(r_set, vtype=GRB.BINARY, name='x')  # tracks whether route r is used\n",
    "y = mdl.addVars(rv_set, vtype=GRB.BINARY, name='y')  # tracks whether route r is assigned to van v\n",
    "z = mdl.addVars(v_set, vtype=GRB.BINARY, name='z')  # tracks whether van v is used\n",
    "s = mdl.addVars(r_set, lb=earliest_time, ub=latest_time, vtype=GRB.CONTINUOUS, name='s')  # tracks start time of route r\n",
    "e = mdl.addVars(r_set, lb=earliest_time, ub=latest_time, vtype=GRB.CONTINUOUS, name='e')  # tracks end time of route r"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "53a33172",
   "metadata": {},
   "source": [
    "## Constraints"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "225d8693",
   "metadata": {},
   "source": [
    "We know that each order is covered by one route and each route can have multiple orders. So, we first establish this relationship, ensuring that when an order is covered, the route that it belongs to should be used.\n",
    "\n",
    "\\begin{align}\n",
    "&a_{o,r} x_{r} = u_{o} &\\quad \\forall o \\in O, r \\in R^o \\tag{1}\\\\\n",
    "\\end{align}\n",
    "\n",
    "Here, $R^o$, shows the routes that only cover order $o$.  \n",
    "There are other ways to show this relationship in mathematical notation. For example, we can use the formulation below which is more generalizable for cases when there are multiple different routes that cover a given order.\n",
    "\n",
    "\\begin{align}\n",
    "&\\sum_{r} a_{o,r} x_{r} = u_{o} &\\quad \\forall o \\in O \\\\\n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "fe03af94-b72d-440c-b81d-e1de82eed7c6",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:15:10.927709Z",
     "start_time": "2023-11-06T20:15:10.913389Z"
    }
   },
   "outputs": [],
   "source": [
    "# Relation between x and u\n",
    "for o, r in order_route_dict.items():\n",
    "    mdl.addConstr(x[r] == u[o], f'order_cov_{o}'); # add \";\" here to stop the cell to print the constraints\n",
    "\n",
    "# # More generalizable version for cases when an order can be in multiple routes\n",
    "# for o, routes in order_route_dict.items():  # in this case, order_route_dict has a signature of {order: list of routes}\n",
    "#     mdl.addConstr(gp.quicksum(x[r] for r in routes) == u[o], f'order_cov_{o}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "db534a31",
   "metadata": {},
   "source": [
    "Similarly, we know that if a route is used, it should be assigned to only one van:\n",
    "\n",
    "\\begin{align}\n",
    "&\\sum_{v} y_{r,v} = x_{r} &\\quad \\forall r \\in R \\tag{2}\\\\\n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "e0b73d5f",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:15:12.405708Z",
     "start_time": "2023-11-06T20:15:12.393027Z"
    }
   },
   "outputs": [],
   "source": [
    "# Relation between y and x\n",
    "mdl.addConstrs((y.sum(r, '*') == x[r] for r in routes_dict), 'route_cov');"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "28688fc6",
   "metadata": {},
   "source": [
    "Next, we focus on van usage, i.e., $z_{v}$.\n",
    "If a van is not used, no routes can be assigned to it. On the other hand, if a van is used, then at least one route should be assigned to it.\n",
    "\n",
    "\\begin{align}\n",
    "&y_{r,v} \\le z_{v} &\\quad \\forall r \\in R, v \\in V \\tag{3}\\\\\n",
    "\\end{align}\n",
    "\n",
    "\\begin{align}\n",
    "&\\sum_{r} y_{r,v} \\ge z_{v} &\\quad \\forall v \\in V \\tag{4}\\\\\n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "ba4e366d",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:15:13.929140Z",
     "start_time": "2023-11-06T20:15:13.918659Z"
    }
   },
   "outputs": [],
   "source": [
    "# LB relation between y and z\n",
    "mdl.addConstrs((y[r, v] <= z[v] for (r, v) in rv_set), 'lb_y_z')\n",
    "\n",
    "# UB relation between y and z\n",
    "mdl.addConstrs((y.sum('*', v) >= z[v] for v in v_set), 'ub_y_z');"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "718a8ac0",
   "metadata": {},
   "source": [
    "Next, we establish the logical constraints for the route's start and end time.  \n",
    "The start time of a route $r \\in R$ ($s_r$) must be between the route's earliest and latest start time ($b^E_r$ and $b^L_r$, respectively).  \n",
    "Similarly the end time of route $r \\in R$ ($e_r$) must be between the route's earliest and latest end time ($f^E_r$ and $f^L_r$, respectively).  \n",
    "Moreover, the route's start and end times have a relation with each other. Namely, the route's end time is equal to the route's start time plus the total duration.\n",
    "\n",
    "\\begin{align}\n",
    "&b^{E}_{r} \\le s_{r} \\le b^{L}_{r} &\\quad \\forall r \\in R \\tag{5}\\\\\n",
    "&f^{E}_{r} \\le e_{r} \\le f^{L}_{r} &\\quad \\forall r \\in R \\tag{6}\\\\\n",
    "&s_{r} + t_{r} = e_{r} &\\quad \\forall r \\in R \\tag{7}\n",
    "\\end{align}\n",
    "\n",
    "**Note**  \n",
    "$s_r$ and $e_r$ only assume meaningful values for routes that are used (i.e., for routes where $x_r = 1$). \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "fbda944d",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:15:15.300790Z",
     "start_time": "2023-11-06T20:15:15.291729Z"
    }
   },
   "outputs": [],
   "source": [
    "# LB of s\n",
    "mdl.addConstrs((s[r] >= routes_dict[r]['Earliest Start Time'] for r in r_set), 'lb_s')\n",
    "\n",
    "# UB of s\n",
    "mdl.addConstrs((s[r] <= routes_dict[r]['Latest Start Time']  for r in r_set), 'ub_s')\n",
    "\n",
    "# LB of e\n",
    "mdl.addConstrs((e[r] >= routes_dict[r]['Earliest End Time'] for r in r_set), 'lb_e')\n",
    "\n",
    "# UB of e\n",
    "mdl.addConstrs((e[r] <= routes_dict[r]['Latest End Time'] for r in r_set), 'ub_e')\n",
    "\n",
    "# relation between s and e\n",
    "mdl.addConstrs((s[r] + routes_dict[r]['Total Time'] == e[r]  for r in r_set), 'rel_s_e');"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2cc5f120",
   "metadata": {},
   "source": [
    "We need another set of constraints to establish the relationship between different routes assigned to a van. Without these constraints, nothing stops the model from assigning all the routes to one van.\n",
    "\n",
    "For any two routes, if one of them is assigned to a van, the other route can only be assigned to the same van if either its start time occurs after the end time of the first route or its end time occurs before the start time of the first route.\n",
    "\n",
    "Using indexes of $r \\in R$ and $h \\in R$ to refer to any two routes ($r \\ne h$), we need a way to say:\n",
    "\n",
    "For all $r \\in R$ and $h \\in R$ ($r \\neq h$), if there exists $v \\in V$ such that $y_{r,v} = 1$ and $y_{h,v} = 1$, then either $s_h \\geq e_r$ or $s_r \\geq e_h$.\n",
    "\n",
    "In other words, we want to say:\n",
    "- If two routes $r$ and $h$ are both assigned to the same van, then only one of the two constraints should be active\n",
    "- If neither route $r$ nor route $h$ are assigned to the same van, the constraints should be inactive\n",
    "\n",
    "Because we have an \"Either-Or\" structure between the two constraints, we use an indicator variable that when takes a value of 1, activates the first constraints and if it takes a value of 0, activates the second constraint. Let's call this indicator variable $\\delta_{r,h}$ and define it as follows:\n",
    "\n",
    "- $\\delta_{r,h}\\quad$: A binary variable equal to 1 if route $r \\in R$ and $h \\in R$ are served by the same van **and route $r$ comes before route $h$**\n",
    "\n",
    "\n",
    "With the definition of $\\delta_{r,h}$, we can simplify our logic as follows:\n",
    "\\begin{align}\n",
    "\\text{if} \\quad \\delta_{r,h} = 1 \\rightarrow s_h \\ge e_r \\quad \\forall r \\in R, h \\in R: r < h \\\\\n",
    "\\text{if} \\quad \\delta_{h,r} = 1 \\rightarrow s_r \\ge e_h \\quad \\forall r \\in R, h \\in R: r < h\n",
    "\\end{align}\n",
    "\n",
    "Now, using the **BigM method** we can write these constraints:\n",
    "\n",
    "\\begin{align}\n",
    "  s_h \\ge e_r - M(1 - \\delta_{r,h}) \\quad \\forall r \\in R, h \\in R : r < h \\tag{8}\\\\\n",
    "  s_r \\ge e_h - M(1 - \\delta_{h,r}) \\quad \\forall r \\in R, h \\in R : r < h \\tag{9}\\\\\n",
    "\\end{align}\n",
    "\n",
    "Moreover, we write the constraint that defines $\\delta$ based on $y$:\n",
    "\n",
    "\\begin{align}\n",
    "y_{r,v} + y_{h,v} - 1 \\leq \\delta_{r,h} + \\delta_{h,r} \\quad \\forall r \\in R, h \\in R, v \\in V: r < h \\tag{10}\\\\\n",
    "\\end{align}\n",
    "\n",
    "This constraint says that if there exists $v \\in V$ such that $y_{r,v} = y_{h,v} = 1$, then either $\\delta_{r,h}$ or $\\delta_{h,r}$ will be forced to equal $1$.  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "455b4685",
   "metadata": {},
   "source": [
    "**Constraints Analysis**:  \n",
    "\n",
    "Consider any two routes $r,h \\in R$ and suppose they are both assigned to van $v \\in V$. If $\\delta_{r,h} = 1$ (and consequently, $\\delta_{h,r} = 0$), that should mean route $r$ comes before route $h$. In this case, the first two constraints reduce to: \n",
    "\n",
    "\\begin{align}\n",
    "  s_h \\ge e_r  \\quad \\forall r \\in R, h \\in R : r < h \\\\\n",
    "  s_r \\ge e_h - M \\quad \\forall r \\in R, h \\in R : r < h \\\\\n",
    "\\end{align}\n",
    "\n",
    "The first constraint simply says that route $h$ should start after route $r$ finishes, which is what we want.  \n",
    "The second constraint has a large negative right-hand-side which makes it non-binding, ineffective, or redundant.\n",
    "\n",
    "Note that these two constraints, along with constraint 7, also ensure that both $\\delta_{r,h}$ and $\\delta_{h,r}$ don't take a value of 1 simultaneously. Because it's not possible for the start of route $h$ to be after end of route $r$ and also, end of route $h$ be before the start of route $r$.\n",
    "\n",
    "Similarly, if neither route $r$ or $h$ are assigned to van $v$, then both of those constraints are non-binding due to large values of $M$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "f3fc4ec8",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:15:17.803980Z",
     "start_time": "2023-11-06T20:15:17.798553Z"
    }
   },
   "outputs": [],
   "source": [
    "rh_set = set((r1, r2) for r1 in r_set for r2 in r_set if r1 != r2)  # pair of (r,h) index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "db331279",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:15:18.251527Z",
     "start_time": "2023-11-06T20:15:18.245159Z"
    }
   },
   "outputs": [],
   "source": [
    "delta = mdl.addVars(rh_set, vtype=GRB.BINARY, name='d')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "8c0a3030",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:15:18.599607Z",
     "start_time": "2023-11-06T20:15:18.579425Z"
    }
   },
   "outputs": [],
   "source": [
    "# Relation between any pair of routes assigned to a van\n",
    "big_m = latest_time\n",
    "for (r, h) in rh_set:\n",
    "    if r < h:\n",
    "        mdl.addConstr(s[h] >= e[r] - big_m * (1 - delta[r, h]), f'rbh_{r}_{h}')  # r before h\n",
    "        mdl.addConstr(s[r] >= e[h] - big_m * (1 - delta[h, r]), f'hbr_{r}_{h}')  # h before r\n",
    "        \n",
    "        for v in v_set:\n",
    "            mdl.addConstr(y[r, v] + y[h, v] - 1 <= delta[r, h] + delta[h, r], f'rel_d_y_{r}_{h}_{v}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4bac0639",
   "metadata": {},
   "source": [
    "There is an alternative way to write the above constraints with the $M$ terms, taking advantage of gurobi's syntax.\n",
    "We can simply tell gurobi that the constraints should only be valid if the respective $\\delta$ variable takes a value of 1. Namely:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "f3fbe25a",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:15:19.599375Z",
     "start_time": "2023-11-06T20:15:19.583911Z"
    }
   },
   "outputs": [],
   "source": [
    "for (r, h) in rh_set:\n",
    "    if r < h:\n",
    "        mdl.addConstr((delta[r,h] == 1) >> (s[h] >= e[r]), f'rbh_{r}_{h}')  # r before h\n",
    "        mdl.addConstr((delta[h,r] == 1) >> (s[r] >= e[h]), f'hbr_{r}_{h}')  # h before r\n",
    "        # only repeating the constraint below, in case you want to try the model by running this cell instead of the one above\n",
    "        for v in v_set:\n",
    "            mdl.addConstr(y[r, v] + y[h, v] - 1 <= delta[r, h] + delta[h, r], f'rel_d_y_{r}_{h}_{v}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "90b4f56e",
   "metadata": {},
   "source": [
    "**NOTE: Either run the cells with BigM formulation or the above one with the indicator variables, not both.**\n",
    "\n",
    "**Tip**:\n",
    "Even though the BigM method is generic, Gurobi's syntax has two advantages over the traditional BigM method.\n",
    "1. In most cases, it's more intuitive since the syntax is closer to how we think about the constraints.\n",
    "2. In large problems, it performs better since Gurobi can extract a much tighter BigM value(s) based on the structure of the model.\n",
    "  - _Extra_: Gurobi could reformulate indicator constraints into [SOS1 constraints](https://www.gurobi.com/documentation/current/refman/constraints.html#subsubsection:SOSConstraints) or BigM constraints. It depends on the $M$ Gurobi is given (or able to derive)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a9e0d5df",
   "metadata": {},
   "source": [
    "## Objectives"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cafeb700",
   "metadata": {},
   "source": [
    "In this model, we have two objectives:\n",
    "1. Maximize order coverage\n",
    "2. Minimize resource/van usage\n",
    "\n",
    "\\begin{align}\n",
    "\\max \\sum_{o} u_{o}\\\\\n",
    "\\min \\sum_{v} z_{v}\\\\\n",
    "\\end{align}\n",
    "\n",
    "We want to give a higher priority to the first objective. To use gurobi's multi-objective syntax, we can have one sense (i.e., minimize or maximize). This is easy since $\\max f(x) = \\min - f(x)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "a7352d11",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:15:25.091274Z",
     "start_time": "2023-11-06T20:15:25.080921Z"
    }
   },
   "outputs": [],
   "source": [
    "mdl.ModelSense = GRB.MINIMIZE\n",
    "# weight=1: minimize, -1: maximize\n",
    "mdl.setObjectiveN(u.sum(), index=0, priority=2, name='order_coverage', weight=-1)\n",
    "mdl.setObjectiveN(z.sum(), index=1, priority=1, name='resource_usage', weight=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "93782ff9",
   "metadata": {},
   "source": [
    "We can now tell Gurobi that the model is complete and it can solve the problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "9b4669ff",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:15:26.220011Z",
     "start_time": "2023-11-06T20:15:26.126793Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (win64)\n",
      "\n",
      "CPU model: 11th Gen Intel(R) Core(TM) i7-1185G7 @ 3.00GHz, instruction set [SSE2|AVX|AVX2|AVX512]\n",
      "Thread count: 4 physical cores, 8 logical processors, using up to 8 threads\n",
      "\n",
      "Optimize a model with 135 rows, 60 columns and 412 nonzeros\n",
      "Model fingerprint: 0xb260da79\n",
      "Model has 20 general constraints\n",
      "Variable types: 10 continuous, 50 integer (50 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 6e+02]\n",
      "  Objective range  [1e+00, 1e+00]\n",
      "  Bounds range     [1e+00, 6e+02]\n",
      "  RHS range        [1e+00, 6e+02]\n",
      "  GenCon coe range [1e+00, 1e+00]\n",
      "\n",
      "---------------------------------------------------------------------------\n",
      "Multi-objectives: starting optimization with 2 objectives ... \n",
      "---------------------------------------------------------------------------\n",
      "\n",
      "Multi-objectives: applying initial presolve ...\n",
      "---------------------------------------------------------------------------\n",
      "\n",
      "Presolve removed 86 rows and 9 columns\n",
      "Presolve time: 0.01s\n",
      "Presolved: 49 rows and 51 columns\n",
      "---------------------------------------------------------------------------\n",
      "\n",
      "Multi-objectives: optimize objective 1 (order_coverage) ...\n",
      "---------------------------------------------------------------------------\n",
      "\n",
      "Found heuristic solution: objective 0.0000000\n",
      "Presolve removed 32 rows and 33 columns\n",
      "Presolve time: 0.00s\n",
      "Presolved: 17 rows, 18 columns, 69 nonzeros\n",
      "Variable types: 0 continuous, 18 integer (18 binary)\n",
      "Found heuristic solution: objective -7.0000000\n",
      "\n",
      "Root relaxation: cutoff, 0 iterations, 0.00 seconds (0.00 work units)\n",
      "\n",
      "Explored 1 nodes (0 simplex iterations) in 0.05 seconds (0.00 work units)\n",
      "Thread count was 8 (of 8 available processors)\n",
      "\n",
      "Solution count 2: -7 0 \n",
      "No other solutions better than -7\n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective -7.000000000000e+00, best bound -7.000000000000e+00, gap 0.0000%\n",
      "---------------------------------------------------------------------------\n",
      "\n",
      "Multi-objectives: optimize objective 2 (resource_usage) ...\n",
      "---------------------------------------------------------------------------\n",
      "\n",
      "\n",
      "Loaded user MIP start with objective 3\n",
      "\n",
      "Presolve removed 36 rows and 33 columns\n",
      "Presolve time: 0.00s\n",
      "Presolved: 14 rows, 18 columns, 51 nonzeros\n",
      "Variable types: 0 continuous, 18 integer (18 binary)\n",
      "\n",
      "Root relaxation: cutoff, 8 iterations, 0.00 seconds (0.00 work units)\n",
      "\n",
      "    Nodes    |    Current Node    |     Objective Bounds      |     Work\n",
      " Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time\n",
      "\n",
      "     0     0     cutoff    0         3.00000    3.00000  0.00%     -    0s\n",
      "\n",
      "Explored 1 nodes (8 simplex iterations) in 0.07 seconds (0.00 work units)\n",
      "Thread count was 8 (of 8 available processors)\n",
      "\n",
      "Solution count 1: 3 \n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 3.000000000000e+00, best bound 3.000000000000e+00, gap 0.0000%\n",
      "\n",
      "---------------------------------------------------------------------------\n",
      "Multi-objectives: solved in 0.08 seconds (0.00 work units), solution count 2\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# mdl.write('ra.lp')\n",
    "mdl.optimize()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f9a1a8f4",
   "metadata": {},
   "source": [
    "## Post Processing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "1f1b8fd1",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:15:29.170677Z",
     "start_time": "2023-11-06T20:15:29.142653Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "All Covered!\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Resource Number</th>\n",
       "      <th>Route Number</th>\n",
       "      <th>Start Time</th>\n",
       "      <th>Technician Name</th>\n",
       "      <th>Origin Location</th>\n",
       "      <th>Total Travel Time</th>\n",
       "      <th>Total Processing Time</th>\n",
       "      <th>Total Time</th>\n",
       "      <th>Earliest Start Time</th>\n",
       "      <th>Latest Start Time</th>\n",
       "      <th>Earliest End Time</th>\n",
       "      <th>Latest End Time</th>\n",
       "      <th>Num Jobs</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>0</td>\n",
       "      <td>4</td>\n",
       "      <td>0.0</td>\n",
       "      <td>Ed</td>\n",
       "      <td>Heidelberg</td>\n",
       "      <td>134.0</td>\n",
       "      <td>60.0</td>\n",
       "      <td>194.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>113.0</td>\n",
       "      <td>194.0</td>\n",
       "      <td>307.0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>0</td>\n",
       "      <td>5</td>\n",
       "      <td>315.0</td>\n",
       "      <td>Flor</td>\n",
       "      <td>Freiburg im Breisgau</td>\n",
       "      <td>90.0</td>\n",
       "      <td>60.0</td>\n",
       "      <td>150.0</td>\n",
       "      <td>195.0</td>\n",
       "      <td>315.0</td>\n",
       "      <td>345.0</td>\n",
       "      <td>465.0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>0.0</td>\n",
       "      <td>Bob</td>\n",
       "      <td>Heidelberg</td>\n",
       "      <td>100.0</td>\n",
       "      <td>30.0</td>\n",
       "      <td>130.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>100.0</td>\n",
       "      <td>130.0</td>\n",
       "      <td>230.0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>178.0</td>\n",
       "      <td>Doris</td>\n",
       "      <td>Freiburg im Breisgau</td>\n",
       "      <td>141.0</td>\n",
       "      <td>120.0</td>\n",
       "      <td>341.0</td>\n",
       "      <td>58.0</td>\n",
       "      <td>178.0</td>\n",
       "      <td>399.0</td>\n",
       "      <td>519.0</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>0.0</td>\n",
       "      <td>Albert</td>\n",
       "      <td>Heidelberg</td>\n",
       "      <td>334.0</td>\n",
       "      <td>90.0</td>\n",
       "      <td>570.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>6.0</td>\n",
       "      <td>570.0</td>\n",
       "      <td>600.0</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   Resource Number  Route Number  Start Time Technician Name  \\\n",
       "1                0             4         0.0              Ed   \n",
       "4                0             5       315.0            Flor   \n",
       "2                1             2         0.0             Bob   \n",
       "3                1             3       178.0           Doris   \n",
       "0                2             1         0.0          Albert   \n",
       "\n",
       "        Origin Location  Total Travel Time  Total Processing Time  Total Time  \\\n",
       "1            Heidelberg              134.0                   60.0       194.0   \n",
       "4  Freiburg im Breisgau               90.0                   60.0       150.0   \n",
       "2            Heidelberg              100.0                   30.0       130.0   \n",
       "3  Freiburg im Breisgau              141.0                  120.0       341.0   \n",
       "0            Heidelberg              334.0                   90.0       570.0   \n",
       "\n",
       "   Earliest Start Time  Latest Start Time  Earliest End Time  Latest End Time  \\\n",
       "1                  0.0              113.0              194.0            307.0   \n",
       "4                195.0              315.0              345.0            465.0   \n",
       "2                  0.0              100.0              130.0            230.0   \n",
       "3                 58.0              178.0              399.0            519.0   \n",
       "0                  0.0                6.0              570.0            600.0   \n",
       "\n",
       "   Num Jobs  \n",
       "1         1  \n",
       "4         1  \n",
       "2         1  \n",
       "3         2  \n",
       "0         2  "
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "res_df = pd.DataFrame()\n",
    "status = mdl.status\n",
    "if status == GRB.OPTIMAL:\n",
    "    res_list = []\n",
    "    for k, val in y.items():\n",
    "        if val.x > 0.5:\n",
    "            rid, n = k  # route id, resource number\n",
    "            r = routes_dict[rid]\n",
    "            st = s[rid].x  # start time\n",
    "            rows = {'Resource Number': n, 'Route Number': rid, 'Start Time': st}\n",
    "            rows.update(r)\n",
    "            res_list.append(rows)\n",
    "    res_df = pd.DataFrame(res_list)\n",
    "    res_df = res_df.sort_values(by=['Resource Number', 'Start Time', 'Route Number'])\n",
    "    uncovered_orders = {o for o in order_route_dict if u[o].x < 0.5}\n",
    "    print(f'Uncovered orders: {uncovered_orders}') if uncovered_orders else print('All Covered!')\n",
    "elif status in (GRB.INF_OR_UNBD, GRB.INFEASIBLE):\n",
    "    print('Model is either infeasible or unbounded.')\n",
    "else:\n",
    "    print(f'Status is {status} which is unexpected.')\n",
    "res_df"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a926b3c9",
   "metadata": {},
   "source": [
    "## Putting it all together"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "72c2cba8",
   "metadata": {},
   "source": [
    "**Sets**\n",
    "- $O\\quad$: Set of orders\n",
    "- $R\\quad$: Set of routes\n",
    "- $V\\quad$: Set of resources/vans\n",
    "\n",
    "**Parameters**\n",
    "- $b^{E}_{r}\\quad$: earliest start time of route $r$\n",
    "- $b^{L}_{r}\\quad$: latest start time of route $r$\n",
    "- $f^{E}_{r}\\quad$: earliest end time of route $r$\n",
    "- $f^{L}_{r}\\quad$: latest end time of route $r$\n",
    "- $t_{r}\\quad$: total duration of time on route $r$\n",
    "- $a_{o,r}\\quad$: 1 if order $o$ is covered by route $r$\n",
    "\n",
    "**Variables**\n",
    "- $u_{o}\\quad$: 1 if order $o$ is covered; 0 otherwise\n",
    "- $x_{r}\\quad$: 1 if route $r$ is used; 0 otherwise\n",
    "- $y_{r,v}\\quad$: 1 if route $r$ is assigned to van $v$; 0 otherwise\n",
    "- $z_{v}\\quad$: 1 if van $v$ is used; 0 otherwise\n",
    "- $s_{r}\\quad$: start time of route $r \\in R$\n",
    "- $e_{r}\\quad$: end time of route $r \\in R$\n",
    "- $\\delta_{r,h}\\quad$: 1 if and only if route $r$ and $h$ are served by the same van <u>and route $r$ comes before route $h$</u>; 0 otherwise"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78b9555b",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-10-19T19:10:20.288414Z",
     "start_time": "2022-10-19T19:10:20.268715Z"
    }
   },
   "source": [
    "\\begin{align}\n",
    "&\\max \\sum_{o} u_{o}&\\\\\n",
    "&\\min \\sum_{v} z_{v}&\\\\\n",
    "\\mbox{s.t: }\\\\\n",
    "&\\sum_{r} a_{o,r} x_{r} = u_{o} &\\quad \\forall o \\in O \\tag{1}\\\\\n",
    "&\\sum_{v} y_{r,v} = x_{r} &\\quad \\forall r \\in R \\tag{2}\\\\\n",
    "&y_{r,v} \\le z_{v} &\\quad \\forall r \\in R, v \\in V \\tag{3}\\\\\n",
    "&\\sum_{r} y_{r,v} \\ge z_{v} &\\quad \\forall v \\in V \\tag{4}\\\\\n",
    "&b^{E}_{r} \\le s_{r} \\le b^{L}_{r} &\\quad \\forall r \\in R \\tag{5}\\\\\n",
    "&f^{E}_{r} \\le e_{r} \\le f^{L}_{r} &\\quad \\forall r \\in R \\tag{6}\\\\\n",
    "&s_{r} + t_{r} = e_{r} &\\quad \\forall r \\in R \\tag{7}\\\\\n",
    "&s_h \\ge e_r - M(1 - \\delta_{r,h}) &\\quad \\forall r \\in R, h \\in R : r < h \\tag{8}\\\\\n",
    "&s_r \\ge e_h - M(1 - \\delta_{h,r}) &\\quad \\forall r \\in R, h \\in R : r < h \\tag{9}\\\\\n",
    "&y_{r,v} + y_{h,v} - 1 \\leq \\delta_{r,h} + \\delta_{h,r} &\\quad \\forall r \\in R, h \\in R, v \\in V: r < h \\tag{10}\\\\\n",
    "&u_{o}, x_{r}, y_{r,v}, z_{v}, \\delta_{r,h} \\in \\{0,1\\} &\\quad \\forall o \\in O, r,h \\in R, v \\in V\\tag{11}\\\\\n",
    "&s_{r}, e_{r} \\ge 0  &\\quad \\forall r \\in R \\tag{12}\\\\\n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "63a77b7e",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:15:34.935506Z",
     "start_time": "2023-11-06T20:15:34.917380Z"
    }
   },
   "outputs": [],
   "source": [
    "def resource_assignment(routes, order_routes, resource_limit):\n",
    "    order_route_dict = dict(zip(order_routes['Customer Name'], order_routes['Route ID']))  # a(o,r)\n",
    "    routes_dict = routes.set_index('Route ID').to_dict(orient='index')  # this will help us in creating the constraints\n",
    "    r_set = routes_dict.keys()  # R\n",
    "    v_set = set(range(resource_limit))  # V\n",
    "    rv_set = {(r, v) for r in r_set for v in range(resource_limit)}  # pair of (r,v) index\n",
    "    rh_set = set((r1, r2) for r1 in r_set for r2 in r_set if r1 != r2)  # pair of (r,h) index\n",
    "\n",
    "    mdl = gp.Model('resource_assignment')\n",
    "\n",
    "    # Variables\n",
    "    u = mdl.addVars(order_route_dict.keys(), vtype=GRB.BINARY, name='u')\n",
    "    x = mdl.addVars(routes_dict.keys(), vtype=GRB.BINARY, name='x')\n",
    "    y = mdl.addVars(rv_set, vtype=GRB.BINARY, name='y')\n",
    "    z = mdl.addVars(v_set, vtype=GRB.BINARY, name='z')\n",
    "    s = mdl.addVars(r_set, lb=earliest_time, ub=latest_time, vtype=GRB.CONTINUOUS, name='s')\n",
    "    e = mdl.addVars(r_set, lb=earliest_time, ub=latest_time, vtype=GRB.CONTINUOUS, name='e')\n",
    "    delta = mdl.addVars(rh_set, vtype=GRB.BINARY, name='d')\n",
    "    \n",
    "    # Constraints\n",
    "    # Relation between x and u\n",
    "    for o, r in order_route_dict.items():\n",
    "        mdl.addConstr(x[r] == u[o], f'order_cov_{o}')\n",
    "        \n",
    "    # Relation between y and x\n",
    "    mdl.addConstrs((y.sum(r, '*') == x[r] for r in routes_dict), 'route_cov')\n",
    "    \n",
    "    # LB relation between y and z\n",
    "    mdl.addConstrs((y[r, v] <= z[v] for (r, v) in rv_set), 'lb_y_z')\n",
    "\n",
    "    # UB relation between y and z\n",
    "    mdl.addConstrs((y.sum('*', v) >= z[v] for v in v_set), 'ub_y_z')\n",
    "    \n",
    "    # LB of s\n",
    "    mdl.addConstrs((s[r] >= routes_dict[r]['Earliest Start Time'] for r in r_set), 'lb_s')\n",
    "\n",
    "    # UB of s\n",
    "    mdl.addConstrs((s[r] <= routes_dict[r]['Latest Start Time']  for r in r_set), 'ub_s')\n",
    "\n",
    "    # LB of e\n",
    "    mdl.addConstrs((e[r] >= routes_dict[r]['Earliest End Time'] for r in r_set), 'lb_e')\n",
    "\n",
    "    # UB of e\n",
    "    mdl.addConstrs((e[r] <= routes_dict[r]['Latest End Time'] for r in r_set), 'ub_e')\n",
    "\n",
    "    # relation between s and e\n",
    "    mdl.addConstrs((s[r] + routes_dict[r]['Total Time'] == e[r]  for r in r_set), 'rel_s_e')\n",
    "    \n",
    "    # Relation between any pair of routes assigned to a van\n",
    "    for (r, h) in rh_set:\n",
    "        if r < h:\n",
    "            mdl.addConstr((delta[r,h] == 1) >> (s[h] >= e[r]), f'rbh_{r}_{h}')  # r before h\n",
    "            mdl.addConstr((delta[h,r] == 1) >> (s[r] >= e[h]), f'hbr_{r}_{h}')  # h before r\n",
    "            for v in v_set:\n",
    "                mdl.addConstr(y[r, v] + y[h, v] - 1 <= delta[r, h] + delta[h, r], f'rel_d_y_{r}_{h}_{v}')\n",
    "\n",
    "    # Objectives\n",
    "    mdl.ModelSense = GRB.MINIMIZE\n",
    "    # weight=1: minimize, -1: maximize\n",
    "    mdl.setObjectiveN(u.sum(), index=0, priority=2, name='order_coverage', weight=-1)\n",
    "    mdl.setObjectiveN(z.sum(), index=1, priority=1, name='resource_usage', weight=1)\n",
    "    mdl.setParam(GRB.Param.OutputFlag, 0)  # disable printing the logs\n",
    "    mdl.optimize()\n",
    "\n",
    "    # create output\n",
    "    res_df = pd.DataFrame()\n",
    "    status = mdl.status\n",
    "    if status == GRB.OPTIMAL:\n",
    "        res_list = []\n",
    "        for k, val in y.items():\n",
    "            if val.x > 0.5:\n",
    "                rid, n = k  # route id, resource number\n",
    "                r = routes_dict[rid]\n",
    "                st = s[rid].x  # start time\n",
    "                rows = {'Resource Number': n, 'Route Number': rid, 'Start Time': st}\n",
    "                rows.update(r)\n",
    "                res_list.append(rows)\n",
    "        res_df = pd.DataFrame(res_list)\n",
    "        res_df = res_df.sort_values(by=['Resource Number', 'Start Time', 'Route Number'])\n",
    "        uncovered_orders = {o for o in order_route_dict if u[o].x < 0.5}\n",
    "        print(f'Uncovered orders: {uncovered_orders}') if uncovered_orders else print('All Covered!')\n",
    "    elif status in (GRB.INF_OR_UNBD, GRB.INFEASIBLE):\n",
    "        print('Model is either infeasible or unbounded.')\n",
    "    else:\n",
    "        print(f'Status is {status} which is unexpected.')\n",
    "    return res_df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "6ad4fea9",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:15:36.925866Z",
     "start_time": "2023-11-06T20:15:36.861456Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "**************\n",
      "Running the model with 1 vans\n",
      "**************\n",
      "Uncovered orders: {'Customer7', 'Customer5', 'Customer3', 'Customer1'}\n",
      "**************\n",
      "Running the model with 2 vans\n",
      "**************\n",
      "Uncovered orders: {'Customer5', 'Customer3'}\n",
      "**************\n",
      "Running the model with 3 vans\n",
      "**************\n",
      "All Covered!\n",
      "**************\n",
      "Running the model with 4 vans\n",
      "**************\n",
      "All Covered!\n"
     ]
    }
   ],
   "source": [
    "# run the model with different resource limits\n",
    "all_outputs = []\n",
    "for limit in range(1,5):\n",
    "    print(f'**************\\nRunning the model with {limit} vans\\n**************')\n",
    "    res = resource_assignment(routes, order_routes, limit)\n",
    "    res['Resource Limit'] = limit\n",
    "    all_outputs.append(res)\n",
    "output_df = pd.concat(all_outputs)\n",
    "output_df = output_df[[\"Resource Limit\"] + [col for col in output_df.columns if col != \"Resource Limit\"]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "dda9a673",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:15:39.661382Z",
     "start_time": "2023-11-06T20:15:39.639786Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Resource Limit</th>\n",
       "      <th>Resource Number</th>\n",
       "      <th>Route Number</th>\n",
       "      <th>Start Time</th>\n",
       "      <th>Technician Name</th>\n",
       "      <th>Origin Location</th>\n",
       "      <th>Total Travel Time</th>\n",
       "      <th>Total Processing Time</th>\n",
       "      <th>Total Time</th>\n",
       "      <th>Earliest Start Time</th>\n",
       "      <th>Latest Start Time</th>\n",
       "      <th>Earliest End Time</th>\n",
       "      <th>Latest End Time</th>\n",
       "      <th>Num Jobs</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>2</td>\n",
       "      <td>0.0</td>\n",
       "      <td>Bob</td>\n",
       "      <td>Heidelberg</td>\n",
       "      <td>100.0</td>\n",
       "      <td>30.0</td>\n",
       "      <td>130.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>100.0</td>\n",
       "      <td>130.0</td>\n",
       "      <td>230.0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>3</td>\n",
       "      <td>178.0</td>\n",
       "      <td>Doris</td>\n",
       "      <td>Freiburg im Breisgau</td>\n",
       "      <td>141.0</td>\n",
       "      <td>120.0</td>\n",
       "      <td>341.0</td>\n",
       "      <td>58.0</td>\n",
       "      <td>178.0</td>\n",
       "      <td>399.0</td>\n",
       "      <td>519.0</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>0</td>\n",
       "      <td>2</td>\n",
       "      <td>0.0</td>\n",
       "      <td>Bob</td>\n",
       "      <td>Heidelberg</td>\n",
       "      <td>100.0</td>\n",
       "      <td>30.0</td>\n",
       "      <td>130.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>100.0</td>\n",
       "      <td>130.0</td>\n",
       "      <td>230.0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2</td>\n",
       "      <td>0</td>\n",
       "      <td>3</td>\n",
       "      <td>178.0</td>\n",
       "      <td>Doris</td>\n",
       "      <td>Freiburg im Breisgau</td>\n",
       "      <td>141.0</td>\n",
       "      <td>120.0</td>\n",
       "      <td>341.0</td>\n",
       "      <td>58.0</td>\n",
       "      <td>178.0</td>\n",
       "      <td>399.0</td>\n",
       "      <td>519.0</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0.0</td>\n",
       "      <td>Albert</td>\n",
       "      <td>Heidelberg</td>\n",
       "      <td>334.0</td>\n",
       "      <td>90.0</td>\n",
       "      <td>570.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>6.0</td>\n",
       "      <td>570.0</td>\n",
       "      <td>600.0</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>3</td>\n",
       "      <td>0</td>\n",
       "      <td>4</td>\n",
       "      <td>0.0</td>\n",
       "      <td>Ed</td>\n",
       "      <td>Heidelberg</td>\n",
       "      <td>134.0</td>\n",
       "      <td>60.0</td>\n",
       "      <td>194.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>113.0</td>\n",
       "      <td>194.0</td>\n",
       "      <td>307.0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>0</td>\n",
       "      <td>5</td>\n",
       "      <td>315.0</td>\n",
       "      <td>Flor</td>\n",
       "      <td>Freiburg im Breisgau</td>\n",
       "      <td>90.0</td>\n",
       "      <td>60.0</td>\n",
       "      <td>150.0</td>\n",
       "      <td>195.0</td>\n",
       "      <td>315.0</td>\n",
       "      <td>345.0</td>\n",
       "      <td>465.0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0.0</td>\n",
       "      <td>Albert</td>\n",
       "      <td>Heidelberg</td>\n",
       "      <td>334.0</td>\n",
       "      <td>90.0</td>\n",
       "      <td>570.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>6.0</td>\n",
       "      <td>570.0</td>\n",
       "      <td>600.0</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>0.0</td>\n",
       "      <td>Bob</td>\n",
       "      <td>Heidelberg</td>\n",
       "      <td>100.0</td>\n",
       "      <td>30.0</td>\n",
       "      <td>130.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>100.0</td>\n",
       "      <td>130.0</td>\n",
       "      <td>230.0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>178.0</td>\n",
       "      <td>Doris</td>\n",
       "      <td>Freiburg im Breisgau</td>\n",
       "      <td>141.0</td>\n",
       "      <td>120.0</td>\n",
       "      <td>341.0</td>\n",
       "      <td>58.0</td>\n",
       "      <td>178.0</td>\n",
       "      <td>399.0</td>\n",
       "      <td>519.0</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>4</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0.0</td>\n",
       "      <td>Albert</td>\n",
       "      <td>Heidelberg</td>\n",
       "      <td>334.0</td>\n",
       "      <td>90.0</td>\n",
       "      <td>570.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>6.0</td>\n",
       "      <td>570.0</td>\n",
       "      <td>600.0</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>4</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>0.0</td>\n",
       "      <td>Bob</td>\n",
       "      <td>Heidelberg</td>\n",
       "      <td>100.0</td>\n",
       "      <td>30.0</td>\n",
       "      <td>130.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>100.0</td>\n",
       "      <td>130.0</td>\n",
       "      <td>230.0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>4</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>178.0</td>\n",
       "      <td>Doris</td>\n",
       "      <td>Freiburg im Breisgau</td>\n",
       "      <td>141.0</td>\n",
       "      <td>120.0</td>\n",
       "      <td>341.0</td>\n",
       "      <td>58.0</td>\n",
       "      <td>178.0</td>\n",
       "      <td>399.0</td>\n",
       "      <td>519.0</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>4</td>\n",
       "      <td>3</td>\n",
       "      <td>4</td>\n",
       "      <td>0.0</td>\n",
       "      <td>Ed</td>\n",
       "      <td>Heidelberg</td>\n",
       "      <td>134.0</td>\n",
       "      <td>60.0</td>\n",
       "      <td>194.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>113.0</td>\n",
       "      <td>194.0</td>\n",
       "      <td>307.0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>3</td>\n",
       "      <td>5</td>\n",
       "      <td>315.0</td>\n",
       "      <td>Flor</td>\n",
       "      <td>Freiburg im Breisgau</td>\n",
       "      <td>90.0</td>\n",
       "      <td>60.0</td>\n",
       "      <td>150.0</td>\n",
       "      <td>195.0</td>\n",
       "      <td>315.0</td>\n",
       "      <td>345.0</td>\n",
       "      <td>465.0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   Resource Limit  Resource Number  Route Number  Start Time Technician Name  \\\n",
       "0               1                0             2         0.0             Bob   \n",
       "1               1                0             3       178.0           Doris   \n",
       "1               2                0             2         0.0             Bob   \n",
       "2               2                0             3       178.0           Doris   \n",
       "0               2                1             1         0.0          Albert   \n",
       "0               3                0             4         0.0              Ed   \n",
       "2               3                0             5       315.0            Flor   \n",
       "1               3                1             1         0.0          Albert   \n",
       "3               3                2             2         0.0             Bob   \n",
       "4               3                2             3       178.0           Doris   \n",
       "2               4                0             1         0.0          Albert   \n",
       "4               4                1             2         0.0             Bob   \n",
       "1               4                1             3       178.0           Doris   \n",
       "0               4                3             4         0.0              Ed   \n",
       "3               4                3             5       315.0            Flor   \n",
       "\n",
       "        Origin Location  Total Travel Time  Total Processing Time  Total Time  \\\n",
       "0            Heidelberg              100.0                   30.0       130.0   \n",
       "1  Freiburg im Breisgau              141.0                  120.0       341.0   \n",
       "1            Heidelberg              100.0                   30.0       130.0   \n",
       "2  Freiburg im Breisgau              141.0                  120.0       341.0   \n",
       "0            Heidelberg              334.0                   90.0       570.0   \n",
       "0            Heidelberg              134.0                   60.0       194.0   \n",
       "2  Freiburg im Breisgau               90.0                   60.0       150.0   \n",
       "1            Heidelberg              334.0                   90.0       570.0   \n",
       "3            Heidelberg              100.0                   30.0       130.0   \n",
       "4  Freiburg im Breisgau              141.0                  120.0       341.0   \n",
       "2            Heidelberg              334.0                   90.0       570.0   \n",
       "4            Heidelberg              100.0                   30.0       130.0   \n",
       "1  Freiburg im Breisgau              141.0                  120.0       341.0   \n",
       "0            Heidelberg              134.0                   60.0       194.0   \n",
       "3  Freiburg im Breisgau               90.0                   60.0       150.0   \n",
       "\n",
       "   Earliest Start Time  Latest Start Time  Earliest End Time  Latest End Time  \\\n",
       "0                  0.0              100.0              130.0            230.0   \n",
       "1                 58.0              178.0              399.0            519.0   \n",
       "1                  0.0              100.0              130.0            230.0   \n",
       "2                 58.0              178.0              399.0            519.0   \n",
       "0                  0.0                6.0              570.0            600.0   \n",
       "0                  0.0              113.0              194.0            307.0   \n",
       "2                195.0              315.0              345.0            465.0   \n",
       "1                  0.0                6.0              570.0            600.0   \n",
       "3                  0.0              100.0              130.0            230.0   \n",
       "4                 58.0              178.0              399.0            519.0   \n",
       "2                  0.0                6.0              570.0            600.0   \n",
       "4                  0.0              100.0              130.0            230.0   \n",
       "1                 58.0              178.0              399.0            519.0   \n",
       "0                  0.0              113.0              194.0            307.0   \n",
       "3                195.0              315.0              345.0            465.0   \n",
       "\n",
       "   Num Jobs  \n",
       "0         1  \n",
       "1         2  \n",
       "1         1  \n",
       "2         2  \n",
       "0         2  \n",
       "0         1  \n",
       "2         1  \n",
       "1         2  \n",
       "3         1  \n",
       "4         2  \n",
       "2         2  \n",
       "4         1  \n",
       "1         2  \n",
       "0         1  \n",
       "3         1  "
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "output_df"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1863587a",
   "metadata": {},
   "source": [
    "# Further Practice: Model Enhancement\n",
    "Make the following changes to the model:\n",
    "- Considering the input files, the output dataframe is not correct. Can you spot what's wrong about it?\n",
    "  - _Hint_: The fix is very easy and you don't need to change the mathematical model!\n",
    "  - **Answer**: I did nothing about the depots. Technicians are not all stationed at the same depot. Since each depot is independent, we just need to decompose the input data based on depot and run the orders and routes of each depot separately.\n",
    "- Some orders are more important (maybe they are from the premium users) and should be favored.\n",
    "  - **Answer**: Introduce a priority parameter for each order. Then, change the objective function so that rather than $\\sum_{o} u_{o}$ we have $\\sum_{o} p_{o} u_{o}$ where $p_{o}$ is the priority of order $o \\in O$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5f6ce465-db8c-4bc0-87a6-570058d7801c",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.18"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
